help. Very short program!
Author Message
help. Very short program!

Hi!

I wrote a very short program that puts a number into a humangous power
and finding its last 6 digits.  The formula is to devide the power by 2
if it's an even number and square the number i need to put into that
humangous power.  So 2 to the power of 100, is the same as 2 to the
power of 2 to the power of 50, etc...  When it's done i have to devide
it by 100000 and get remainder to find last 6 digits.  The idea is very
simple.  This way it should not take long.  However my program never
finishes running.  It's literally 10 lines long.  Can you please take a
look at it?  Thank you very much!

(define p 647307989872865201422284359961937038113215496061434545237)

(define (square y)
(* y y))

(define (Last6Digits b x)
(remainder (fast_power b x) 1000000))

(define (fast_power a p)
(cond ((= p 0) 1)
((= p 1) a)
((even? p)(fast_power(square a)(/ p 2)))
(else (* a (fast_power a (- p 1))))))

I will appreciate any ideas.  Thanks.

-sergey-

Sat, 16 Mar 2002 03:00:00 GMT
help. Very short program!

Quote:

> Hi!

> I wrote a very short program that puts a number into a humangous power
> and finding its last 6 digits.  The formula is to devide the power by 2
> if it's an even number and square the number i need to put into that
> humangous power.  So 2 to the power of 100, is the same as 2 to the
> power of 2 to the power of 50, etc...  When it's done i have to devide
> it by 100000 and get remainder to find last 6 digits.  The idea is very
> simple.  This way it should not take long.  However my program never
> finishes running.  It's literally 10 lines long.  Can you please take a
> look at it?  Thank you very much!

If p below is power, then it is easy to understand why you have to wait
long before the stop (maybe few million years will be ok ?). BTW it
would be better to not duplicate global name with p parameter name below
- it makes things less clear.

I'm not sure what you are trying to do, but if you are trying only to
get last 6 digits, then take another route. Generally truncucate excess
digits (> 6) after each multiplication. This way you will fit into basic
integer.

If you want to speed things up, multiply by few powers at once - but
take care to not cross into bigintegers, as it can slow things down
considerably.

OR, go to high power in steep manner - each time working on quite large
integers - like 40-100 digits, but also truct after each step.

Artur

Sat, 16 Mar 2002 03:00:00 GMT
help. Very short program!

Quote:

> Hi!

> I wrote a very short program that puts a number into a humangous power
> and finding its last 6 digits.  The formula is to devide the power by 2
> if it's an even number and square the number i need to put into that
> humangous power.  So 2 to the power of 100, is the same as 2 to the
> power of 2 to the power of 50, etc...  When it's done i have to devide
> it by 100000 and get remainder to find last 6 digits.  The idea is very
> simple.  This way it should not take long.  However my program never
> finishes running.  It's literally 10 lines long.  Can you please take a
> look at it?  Thank you very much!

> (define p 647307989872865201422284359961937038113215496061434545237)

> (define (square y)
>   (* y y))

> (define (Last6Digits b x)
>   (remainder (fast_power b x) 1000000))

> (define (fast_power a p)
>   (cond ((= p 0) 1)
>         ((= p 1) a)
>         ((even? p)(fast_power(square a)(/ p 2)))
>         (else (* a (fast_power a (- p 1))))))

> I will appreciate any ideas.  Thanks.

> -sergey-

I think you (non-terminaison) probleme comes from (/ p 2)
that does not return an integer (e.g. (/ 15 2) => 7.5)