Viewing a single comment thread. View all comments

AquaRegia t1_j23vf57 wrote

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

2838393^(72829) is 72,828 multiplications resulting in a number with 469,965 digits. A 64-bit processor can't directly work with numbers larger than 20 digits, which means it'll have to perform multiple operations for a single multiplication.

All in all, it's not enough that modern computers are really fast, if it just tried to brute-force the calculation it'd still take a lot of time.

1

nmxt t1_j23weu9 wrote

Well it’s not 72,828 multiplications, it’s something like thirty multiplications. If 2838393 is N, you first need to calculate N^2 , then N^4 as the previous result squared, then N^8 as N^4 squared etc. and then just multiply some of those power-of-two results to combine them into the required final power. For example, if you wanted to calculate 3^9, you don’t need to make 9 multiplications. You calculate 3^2, 3^4 and 3^8 (three multiplications), and then multiply 3^8 by 3 to get 3^9 (fourth multiplication).

2