Re: Learning recursion with hailstone seqence

"DAVID B MORGAN" <lepton2@xxxxxxxxxxx> wrote in message
news:J%47h.3638$v93.2468@xxxxxxxxxxx

I'm playing with the hailstone sequence. My function will need to
iterate millions of times to process the data. ...

function hailstone(x:int64):int64;
begin
if odd(x) then result:=x*3+1
else result:=x shr 1;
if result<>1 then hailstone(result) ;
end;

1. Can this function be optimised ? (approx 2^67 iterations are
neccessary on current dataset)

It's tail-recursive. You can rewrite it as a loop. Other than that,
there really isn't much room for optimisation - it's a very short
and easy function.

Perhaps using shorter values or using MMX in some way, but I'm not
qualified to say anything about that.


2. How can I test huge numbers (like 2^1000) --- Int64 can't handle it

Having only four operations, it should not be very hard to write an
extended precision library for just this problem.

I'd suggest using a static array of (unsigned) integers for the value
itself, and an extra counter to keep track of the position of the first
1 bit in the value. That should be almost free, and make the fourth
operation a lot cheaper.

As an aside, I can confidently predict that for 2^1000, the return value
of the above function is 2^999 after recursing exactly 999 times.

Groetjes,
Maarten Wiltink


.

Relevant Pages

  • Re: Learning recursion with hailstone seqence
    ... need to iterate millions of times to process the data. ... else result:=x shr 1; ... A Hailstone sequence is the sequence of integers, ... without contributing to the result. ...
    (comp.lang.pascal.delphi.misc)
  • Re: Newbie: Help Figger Out My Problem
    ... It may be shorter but it keeps the entire list in memory and has to ... iterate over the list twice! ...
    (comp.lang.python)
  • Re: Learning recursion with hailstone seqence
    ... need to iterate millions of times to process the data. ... else result:=x shr 1; ... Count on a recursion depth of 50 times the bit-length of x. ... Tom ...
    (comp.lang.pascal.delphi.misc)