GCD

Pages: 12
Aug 10, 2018 at 2:29pm
I did this...
auto big = pow(1000000000, 1000000000);

I wanted to see what big would be. I discovered there is no container that can store a number like that. inf is treated as a stupid double. :(
Aug 10, 2018 at 2:35pm
3000 = 2^3 * 3 * 5^3
so
3000^1000000000 = 2^3000000000 * 3^1000000000 * 5^3000000000
2^3000000000 by itself is much, much greater than the upper limit of double, 2^2048 (give or take 50 powers).

Doing a little math with logarithms, you can get that in order to represent 3000^1000000000 exactly, you need approximately 3.48 billion decimal digits, or 1.34 GiB. You need exact representations to perform integer arithmetic and not get garbage out.
Aug 11, 2018 at 6:37pm
Just an observation, but...

If (a-b) = 0 then GCD = 2a^n.
If (a-b) = 1 then GCD = 1.

Things get tricky if abs(a-b) is greater than 1.
Topic archived. No new replies allowed.
Pages: 12