factorial and exponent

[Army1987]

Army1987 said:

Correct.

So references which claim that a regular polygon of n sides is
constructible if and only if all the odd prime factors of n are
distinct Fermat primes (e.g. Wikipedia) must be wrong, since
2^100000000 * 3 * 17 * 257 is such a number, but such a polygon
cannot be constructed.

(Or the limits of an algorithm are not the same thing as the limits
of its implementation, nor even the same thing as the limits of the
universe.)

 

[Richard Heathfield]

Army1987 said:

So references which claim that a regular polygon of n sides is
constructible if and only if all the odd prime factors of n are
distinct Fermat primes (e.g. Wikipedia) must be wrong, since
2^100000000 * 3 * 17 * 257 is such a number, but such a polygon
cannot be constructed.

That depends on their definition of "constructible". As for Wikipedia
being wrong, that wouldn't particularly shock me.

 

[Tom Gear]

I want to calculate the value of 126 raise to the power 126 in turbo
C.
I've checked it with unsigned long int but it doesn't help.
So how could one calculate the value of such big numbers?
What's the technique?

Hi. This is similar to a programming project I'm doing in assembler.

I think the first thing you need to do, and I think someone else
mentioned this, is to find out the size of the final result. Then
make sure you feed the result there. You do this by using natural
logarithms, but I forget how, I had to ask my son. Convert 126^126
base ten = 2^ whatever.

I think you might consider bit shifting since 126 = 128 - 2.

128 = 1000 0000. So that would be shift left seven.
2 = 10. Shift left once.

Initialize your source=126. What you do is shift your source left
seven, add to a scratch area, shift it right 6, subtract from scratch,
voila you've just multiplied your source by 126. This becomes your new
source. Loop 126 times.

 

[Eric Sosman]

Tom Gear wrote On 06/27/07 14:21,:

Hi. This is similar to a programming project I'm doing in assembler.

I think the first thing you need to do, and I think someone else
mentioned this, is to find out the size of the final result. Then
make sure you feed the result there. You do this by using natural
logarithms, but I forget how, I had to ask my son. Convert 126^126
base ten = 2^ whatever.

You should be able to do this in your head, to a
reasonable approximation.

lg(126^126)
= 126*lg(126)
~= 126*lg(128)
= 126 * 7
= 882

Replacing 126 by 128 errs on the high side, so the
approximation cannot be too small. (It turns out --
I cheated and used a calculator -- that 880 bits will
suffice; the estimate is high by <0.23%.)

I think you might consider bit shifting since 126 = 128 - 2.
[...]

See TAOCP section 4.6.3 for efficient computation of
powers.