Hey /sci/. I was wondering if there was an absolute most efficient way to multiply large numbers together, by hand.
Without resulting to a calculator, how can I take
a * b
and figure out which c fits to
a * b = c.
What would be the absolute best method or approach to calculate what c is equal to, if you had to do it all by hand.
>>8125757
logs and log tables?
>>8125757
> was wondering if there was an absolute most efficient way to multiply large numbers together
New algorithms (essentially variants of Furer's algorithm) continue to reduce the asymptotic complexity, but Schönhage–Strassen is the fastest algorithm that's actually used in practice (more advanced algorithms are only faster for numbers with billions of digits).
> by hand.
This is a meaningless qualification. For a non-trivial number of digits, the fastest "by hand" algorithm is the same as the fastest computer algorithm, as asymptotic time complexity always beats micro-optimisations eventually.
>>8125761
OP said "large" numbers, which rules out the use of tables (the size of a table is inherently exponential in the number of digits).
Using tables at the base level only gets you a constant factor, it doesn't change the algorithm or the asymptotic complexity.
Schönhage–Strassen
What math does one need to know to perform this function by hand?
>>8125757
Monte Carlo
>>8125783
Addition
>>8125757
The one you learned in grade school. Multiply a by each digit of b. Add the results.
>>8125757
Depends on what you mean by "large", doing it in your head then large is probably 3 or 4 figures, In which case you can brake the number up into smaller chunks, so 132*4 = 13*4*10 + 4*2, which I've always found easier to do.
>>8125783
>Schönhage–Strassen
Fast Fourier Transform
Ability to Google.
Decompose the numbers
Use algebra
Do basic arithmetic
>>8126066
Doing FFTs by hand...
>>8125783
> What math does one need to know to perform this function by hand?
The ability to follow the algorithm at the level of detail to which it is written.
If it treats addition, subtraction, multiplication and division (of fixed-size numbers) as primitive operations, you need to be able to perform those operations.
But there's nothing stopping you from writing the algorithm such that those operations are essentially subroutines, i.e. explaining how to add two numbers together.