0

I want to optimize some division algorithm for large numbers, but this is dependent on how fast i can multiply the divisor with powers of ten: divisor * power(10, n) where n is a positive integer. i know about some optimized multiplication algorithms such as the use of FFT, but that still goes though O(nlog(n)), but am looking for something optimized for this case only, otherwise my algorithm performance will have performance greater than O(nlog(n)). Any idea if there is an optimization for this special case?

Note that i intend to implement this in C++.

maress
  • 3,533
  • 1
  • 19
  • 37
  • 2
    Sadly, I can't help much, but why are you working with powers of ten instead of the more natural powers of two ? – J.N. Mar 12 '12 at 08:32
  • 4
    You might try precalculating `power(10, n)` for the range of values of `n` you might encounter (given there can only be a few thousand before `double`'s range's exhausted): put them into an array for direct indexing by `n`. – Tony Delroy Mar 12 '12 at 08:37
  • 1
    @TonyDelroy: You should put some more details on it and put it as an answer, it is a good solution [IMO], which will probably be easier to implement and faster then FFT or other solutions. – amit Mar 12 '12 at 08:39
  • @J.N: i am not doing multiplication at the digital level, if so, it would have been very easy (shifting the bits in O(n)). Also, the integers i want to work with may have millions of digits. multiplication in binary would also break the algorithm i want to implement besides the fact that the representation of the large integer in binary is cumbersome due to the fact that it is not a single integer but an array of built in integer types. – maress Mar 12 '12 at 08:46
  • @TonyDelroy: Actually it can be much larger, millions of digits. Multiplying several digit number with 10^100 or larger. But this probably is a good idea, can decide to do it in steps lower than the double range – maress Mar 12 '12 at 08:49
  • Frankly I don't see how an indexing approach ( or as a matter of fact, any software approach ) will beat the natural instruction. div while slower than mul still churns heck of a lot faster than table indexing on all architectures I've run into this millennium. If anything I'd take a look at what sort of enhanced instruction set you have access to ( altivec, SSE etc ), and try to vectorize your problem instead. EDIT: Sorry, missed that you need larger range than builtins. – Ylisar Mar 12 '12 at 08:50
  • 2
    If you want to go fast, you have no choice but speaking a language your computer understands, that is binary. Every step of translation will cost you an order of magnitude in performance. – J.N. Mar 12 '12 at 08:51
  • 2
    Providing ideas on how your builtin integer work will help people give you better answers. – J.N. Mar 12 '12 at 08:52
  • the large integer is represented as an array to "base 10^10", that is the largest element in the array can be '10^10 - 1', where element[0] is the least significant element and element[length-1] is the most significant element. I chose that maximum in order to simply addition and subtractions and avoid unsigned integer addition overflow, the most common operations. – maress Mar 12 '12 at 09:22
  • 1
    @maress, `10^10` is approximately `2^(33.2)`. That seems to me as one of the worst possible bases available. Please take the time to elaborate your motivations and constraints. – avakar Mar 12 '12 at 09:36
  • @jgroenen, you've missed the `power(10, n)` part. – avakar Mar 12 '12 at 09:37
  • @jgroenen: thanks! I have been looking for something like this, and could not arrive at that shifting. It seems pretty good, and may be i can tweak my implementation to use a modified version for faster multiplication (in thousands) – maress Mar 12 '12 at 09:41
  • @avakar: it is a matter of representation. certainly i cannot represent a million digit integer as a single digit in modern computers. So i represent it in as an array, with each array component maximum value being (CORRECTION) 10^9 - 1. – maress Mar 12 '12 at 09:44
  • @maress, the thing everyone is questioning is why you didn't choose the maximum value of `2^32`, or even `2^31` if you insist on having room for overflow? Why did you choose such an esoteric base as `10^9`? – avakar Mar 12 '12 at 09:47
  • Check [this](http://stackoverflow.com/questions/2882706/how-can-i-write-a-power-function-myself) out! – Naszta Mar 12 '12 at 09:51
  • @avakar 999,999,999 to be maxmimum, so that i have an easy carry and borrow during addition and subtraction (am doing this operations in base 10 actually). If you can explain why 2^31 = 2147483648 would be more appropriate than what i have chosen for this operations? – maress Mar 12 '12 at 09:55
  • 1
    @maress, because in base `2^31`, to add digits `a` and `b` you simply compute `(a+b)&0x7fffffff` for the result digit and `(a+b)>>31` for carry. That is much faster than `(a+b)%1000000000` and `(a+b)/1000000000`. In other words, dividing by a power of 2 is much faster than dividing by any other number. You should read more about how bigint libraries are done in practice. – avakar Mar 12 '12 at 10:00

1 Answers1

2

If you use array to store large numbers, you can copy the divisor to a new array and add n zeros to the end of it. The new array is the the answer you want. The complexity is O(n).

discover
  • 46
  • 3