Viewing a single comment thread. View all comments

mfb- t1_j23u03n wrote

Reply to comment by AquaRegia in ELI5: How do computers compute gigantic mathematical calculations? by DryEstablishment2

There is a much nicer way to break down exponents:

  • Calculate 2838393^2
  • Calculate (2838393^(2))^2 = 2838393^4 by squaring the previous result
  • Calculate ((2838393^(2))^(2))^2 = 2838393^8 by squaring the previous result
  • ... this produces all powers of 2 we need (2, 4, 8, 16, 32, ... 1024)

x^1087 = x^1024 * x^32 * x^16 * x^8 * x^4 * x^2 * x and all these factors were calculated previously (here for x=2838393).

You only need to square numbers, and at the end multiply a few numbers with each other. The computer stores numbers in binary anyway (so 1087 is 1024+32+16+8+4+2+1 for a computer), no extra steps needed to find the right factors.

(actually, for OP's original problem, a computer would directly use 72829 = 65536 + 4096 + ...)

8

Schnutzel t1_j23vg43 wrote

Also, by using floating point numbers, you can make the calculations a lot faster by sacrificing precision. Instead of storing 2838393^1024 (which is a huge number) you only store the most significant digits and how many digits it has.

2

mfb- t1_j241eji wrote

It depends on the application. 2838393^1024 has 6600 digits, which is no problem for modern computers to calculate exactly in well under a second.

1

Schnutzel t1_j24265s wrote

True, but when the exponent is 76000 and you start multiplying numbers with tens of thousands of digits, it starts to rack up.

1