0

As stated, I'm interested in programs for multiplying and dividing large numbers. I am hardly a novice coder so I can't yet prepare such algorithms myself, and I couldn't find anything on google. As a side question, what are some ballpark estimates of time for multiplying two numbers with say a million plus digits?

user7778287
  • 367
  • 1
  • 11
  • http://mikemcl.github.io/decimal.js/ if you want to make the browser work. Up to 10^9 digits in arithmetics, only 1000 for transcendental functions. – Lutz Lehmann Mar 31 '17 at 06:48
  • take a look at: [Fast bignum square computation](http://stackoverflow.com/q/18465326/2521214) for basics and [Modular arithmetics and NTT (finite field DFT) optimizations](http://stackoverflow.com/q/18577076/2521214) for more advanced (faster for really big numbers) approach Ryan's answer is about ... btw there are libs for this thing out there ... google bigint, bigdecimal, arbitrary precision,... – Spektre Mar 31 '17 at 07:28
  • btw for my Schönhage–Strassen multiplication implementation the threshold is ~44672 bits of result so it starts to be faster then Karatsuba if result has `log(2)*44672 = ~13448` digits which is way bellow your `10^6` of operand... – Spektre Mar 31 '17 at 07:47

1 Answers1

3

Programming languages with built-in big integers are convenient for this. Here’s Python, for example:

>>> import random
>>> a = random.randrange(10**(10**6), 10**(10**6 + 1))
>>> b = random.randrange(10**(10**6), 10**(10**6 + 1))
>>> c = a * b

The multiplication itself takes about half a second on my device (with an i5-7500 processor). Converting the result to a decimal string stored in memory takes somewhat longer, clocking in at around 48 seconds. (If you don’t need decimal, using a base with an efficient conversion from Python’s internal representation will be much faster; hex(c), for example, is instant.) Writing the result to disk will take about 30 seconds if you use two 1.44 MB floppies and aren’t very fast at ejecting/inserting them.

The algorithm behind this is usually Schönhage–Strassen.

Ry-
  • 218,210
  • 55
  • 464
  • 476
  • the printing can be significantly speed-ed up by either using hex view or using `10^n` as digit base ... – Spektre Mar 31 '17 at 07:33
  • @Spektre: I’m not sure that Python supports storing bignums with alternate bases. It’s true that the asker didn’t specify any particular output format, though, so I’ll mention hex. – Ry- Mar 31 '17 at 07:34
  • by `10^n` digit base I mean internal number representation per WORD the print is decadic in that case of coarse. The benefit is that digits do not bleed to other WORDS of number so it is `O(n)` instead of `O(n^2)` printing ... – Spektre Mar 31 '17 at 07:38
  • @Spektre: I know what you mean and I’m saying Python doesn’t support setting the internal representation as far as I know. – Ry- Mar 31 '17 at 07:39