Re: Learning recursion with hailstone seqence

"DAVID B MORGAN" <lepton2@xxxxxxxxxxx> schreef in bericht
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. I have two
questions:

1. Can this function be optimised ? (approx 2^67 iterations are neccessary
on current dataset)
2. How can I test huge numbers (like 2^1000) --- Int64 can't handle it

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;


A Hailstone sequence is the sequence of integers, as defined in your
function, that leads from the original value to 1. AFAIK there is no proof
but it is true for all tested numbers.

What is it your function must return?
a) the result is pretty much meaningless in the current function.
Hailstone(2**n) = n-1. And then the last line of the function will iterate
without contributing to the result.
b) If you change the last line to
if result<>1 then result:=hailstone(result) ;
the function will either return 1 or it will go on forever.

I guess that you want to know how long the sequence of steps is before the
iteration ends.
It would be simpler then to program a loop:
cnt:=0;
repeat
inc(cnt);
if odd(N)
then N:=3*N+1
else N:=N SHR 1;
until (N=1) OR (cnt>maxCnt);

eg for N=123456789012345678, cnt=287 results.

For large integers you will have to store N in an array. Find routines for
this on the web.

Tom


.

Relevant Pages

  • Re: Reinventing the iterator
    ... RST returns the rest of the sequence (lazily) ... The main purpose of SEQ is to give the ability to iterate over various ... just use lists (it's the most simple and ...   "The analog of DOLIST for any collection COLL, ...
    (comp.lang.lisp)
  • Re: Logarithm of repeated exponential
    ... Here's a fairly elementary proof that this sequence ... Image (red is base 3 log iterate): ... you dilate by a fixed amount in the previous term. ... some series are divergent using conventional methods, but convergent using, ...
    (sci.math)
  • Re: Convert active characters into control sequences
    ... large "commenting monologues". ... Macro "\getcsname" takes as it's second argument a sequence ... you could also iterate n by n ...
    (comp.text.tex)
  • Re: Logarithm of repeated exponential
    ... Here's a fairly elementary proof that this sequence ... Image (red is base 3 log iterate): ... this series is probably not convergent "conventionally" (whatever that may mean, ... anyway), but is nevertheless convergent using stronger methods, in the same way ...
    (sci.math)
  • Re: abstract sequences
    ... LOOP breaks the sequence abstraction by requiring different syntax ... The MAP function will iterate over any sequence, ... (defun inverse (vec) ...
    (comp.lang.lisp)