2

I have played around with Big Integer arithmetic for a few months (2+) now and have explored many ways and ideas of implementing it. I have working versions of String based implementations (highly inefficient), base 1e9 and 1e18 (more efficient but still slightly wasteful) and a modular arithmetic based implementation. Currently, I'm working on a new idea I've had in mind. (Note: it might not be a "new" radically different idea for working with big integers but because I've been exploring the concept on my own, it seems new to me. I've never looked at implementations in Boost Multiprecision Library or GNU GMP or any other library and have come up with most algorithms on my own)

The new idea: I'm representing the Big Integer as base 2 in 32-bit slots. The representation includes the 2's complement method.

(Base 10) 100 = (Base 2) 00000000000000000000000001100100

(Base 10) 10000000000000000 = (Base 2) 00000000001000111000011011110010 01101111110000010000000000000000

...and so on for bigger numbers.

This representation is highly efficient in terms of space lost and implementing algorithms in base 2 is a whole lot easier. The only problem I'm facing is the conversion from a huge base 2 Big Integer to base 10 human understandable representation. Currently, I use my base 1e9 Big Integer implementation in conjunction with this in order to do the conversion. However, this is very inefficient and leads to a trade-off between algorithm speeds and high memory costs. I do not want that sort of trade-off to exist. Why should I have to deal with such a high memory cost every time I need to display an integer as every time I need to do so, I'm gonna have to run base 1e9 for calculating and summing up pure powers of 2?

So far, I've not been able to intuitively come up with a clever way of doing the conversion and I would like to have some advice on how to proceed. Is there an efficient way? Can the base 10 representation solely be created by looking at the set bits?

Arrow
  • 389
  • 2
  • 12
  • 4
    Take a look at "Modern Computer Arithmetic", by Brent and Zimmerman. They have a section describing quadratic-time and subquadratic-time base conversion algorithms. PDF available here: https://members.loria.fr/PZimmermann/mca/mca-cup-0.5.9.pdf – Mark Dickinson Oct 01 '20 at 11:19
  • @MarkDickinson I find the PDF very interesting. I've been reading the book for the past two hours straight and it's going to keep me hooked for the next couple of days. I might finally gather the courage to understand FFT and not be daunted by the mathematics behind it like I always have been. Even though I haven't made it to the section you mentioned, I feel like I'm going to be surprised with something that I am exactly looking for. Thanks for the link! I'll reply after I've completed my reading and let you know if I found what I'm looking for. – Arrow Oct 01 '20 at 15:44
  • 1
    how big numbers are you writing about? FFT based approaches are better only for really huge numbers for more info see: [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) specially pay attention to the NTT based stuff in there. However for not so huge numbers are usually less advanced methods faster see [How to convert a gi-normous integer (in string format) to hex format?](https://stackoverflow.com/a/18231860/2521214) and [Algorithm for converting large hex numbers into decimal form (base 10 form)](https://stackoverflow.com/a/45262609/2521214) – Spektre Oct 05 '20 at 10:15
  • @Spektre Hey! Thanks for joining in! I would like to implement an arbitrary multiprecision library as a project some day. I have a lot in my head about the things I want to do with such a library and the numbers I would like to work with could get very big very fast (and I need heavy precision too). I haven't understood all the math behind fourier transforms and the ways it could be carried out but I've got a lot of time (i think) in hand to study. Yes, FFT is only useful when dealing with really huge numbers.Thanks for the links too! I'll make sure to take a look when I'm free from homework. – Arrow Oct 05 '20 at 16:21
  • @Spektre You might want to suggest me to use a pre-existing library reading my previous comment but it's a project I've had in mind since I first learnt programming and the limitations of in-built integer types (C/C++) and I really want this project to see the light of the day. So, until I re-invent the wheel again for myself, I'm not going to be able to drive my cart :) – Arrow Oct 05 '20 at 16:25
  • I do not use 3th party libs for this I got my own. The most useful one I use is fixed size unsigned big integer template which is declared like this: `uint<4> a` where 4 means 4*32 bits ... arbitrary precision is slower. I got libs for fixed point,arbitrary floating and integer and fixed integer. Each used for different tasks. Anyway for arbitrary ones I chose algorithm from the bitwidth on the run to select fastest one using thresholding – Spektre Oct 06 '20 at 05:34
  • if you want to start with FFT see: [How to compute Discrete Fourier Transform?](https://stackoverflow.com/a/26355569/2521214) but strongly suggest to use [NTT](https://stackoverflow.com/q/18577076/2521214) for number crunching to avoid rounding problems and boost speed – Spektre Oct 06 '20 at 05:38

0 Answers0