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)
Check your implementation about this feature

Didier



Thu, 21 Mar 2002 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Help! Very short program

2. long = short*short ; (short,short) = long/short

3. Help needed with writing a short PROGRAM.

4. Duel, Apl, and the shortest program to find prime numbers

5. Short Courses on Object-Oriented Modeling and Programming

6. XBase ++ Short program which demonstrates bug

7. (long) Re: Including ALL Programming Ideas (short)

8. Shortest selfreproducing Forth program

9. Why are functional programs shorter/faster to develop?

10. A short Program, reqest for comments

11. Newbie with questions in very short program

12. What's the shortest possible COBOL program?

 

 
Powered by phpBB® Forum Software