Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: Safety of casting from 'long' to 'int'
Date: Sat, 09 May 2026 06:35:06 -0700
Organization: A noiseless patient Spider
Lines: 157
Message-ID: <86mry8so39.fsf@linuxsc.com>
References: <10su8cn$am9i$1@dont-email.me> <10thrud$1v1r3$1@dont-email.me> <10tibhl$ba1$1@reader1.panix.com> <10tie4h$1l93l$1@dont-email.me> <10tiu79$obc$1@reader1.panix.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 09 May 2026 13:35:10 +0000 (UTC)
Injection-Info: dont-email.me; logging-data="3864365"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+3bCcwDDDF/TuT0txw/EP3kqNdXvUEsLM="; posting-host="241722c71660d3e26e4790da0fa3960c"
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:aKE0zhKA7MtdF9P/FyPlGNaC+aQ= sha1:4nmP+G/J/0ekaPPBD85Sj1PX2B4= sha256:RDGlZf4zPY3neZkBbyfozU0i8Gbvl1Hr4rpqvYaiFLA= sha1:IZ8dtdhSjx6v93MgNM/vbKX5J98=
Xref: csiph.com comp.lang.c:398583

cross@spitfire.i.gajendra.net (Dan Cross) writes:

[some non-C, some C]

> To get a taste for the flavor of SML, you may find
> https://www.cs.cmu.edu/~rwh/isml/book.pdf interesting.
>
> The Fibonacci example that in this "M" language is:
>
> |func fib(n)=
> |     if n<3 then
> |             1
> |     else
> |             fib(n-1)+fib(n-2)
> |     fi
> |end
>
> [sic: as a sequence, the Fibonacci numbers are undefined for
> $n<0$, but this is a pedagogical example, so let's ignore that]

A comment on that further down...

> In SML, this same program could be written as:
>
> ```
> fun fib(n) =
>   if n<3 then
>     1
>   else
>     fib(n-1) + fib(n-2)
> ```
>
> Here I'm trying to follow his style.  Somewhat more
> idiomatically style, would probably be written like:
>
> ```
> fun fib n =
>     if n < 3 then 1
>     else fib (n - 1) + fib (n - 2)
> ```
>
> Though typically one would use pattern matching so as to more
> closely match the mathemtical definition of the Fibonacci
> numbers, expressed as a recurrence relation:
>
> ```
> fun fib 0 = 1
>   | fib 1 = 1
>   | fib n = fib (n - 1) + fib (n - 2)
> ```
>
> (Origin 0, not 1.)

fibonacci(0) is 0.  There is no other.

> But note that so far all of these programs are exponential in
> both space and time.  A more robust version, mirroring Harper's,
> that runs in linear time and space is:
>
> ```
> exception Range of string
>
> fun fib n =
>   let fun fib' 0 = (1, 0)
>         | fib' 1 = (1, 1)
>         | fib' n =
>             let val (a, b) = fib' (n - 1)
>             in (a + b, a)
>             end
>   in if n >= 0
>      then #1 (fib' n)
>      else raise Range "fib: n must be non-negative"
>   end
> ````

Usually the fibonacci function is defined for negative numbers
through the same recurrence relation, so fib(n) is defined in
terms of fib(n+1) and fib(n+2).  Here is (an exponential) fib
written in OCaml:

   let rec fib = function
     | 0            -> 0
     | 1            -> 1
     | k when k > 1 -> fib (k-2) + fib (k-1)
     | k            -> fib (k+2) - fib (k+1)

Incidentally, fibonacci(-n) = fibonacci(n), except with alternating
signs: ..., -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...

> A tail recursive version that runs in linear time and constant
> space is:
>
> ```
> exception Range of string
>
> fun fib n =
>   let fun fib' 0 a _ = a
>         | fib' n a b = fib' (n - 1) (a + b) a
>   in if n >= 0
>      then fib' n 1 0
>      else raise Range "fib: n must be non-negative"
>   end
> ```
>
> Of course, in C, one might write the last as something like:
>
> ```
> unsigned int
> fib(unsigned int n)
> {
>     unsigned int a = 1, b = 0;
>     while (n-- > 0) {
>         unsigned int sum = a + b;
>         b = a;
>         a = sum;
>     }
>     return a;
> }
> ```

Here is my current favorite (for C) linear fibonacci function:

    typedef unsigned long long ULL;

    ULL
    sfibonacci( unsigned n ){
      ULL a = 0, b = 1;
        while(  n > 1  )  a += b,  b += a,  n -= 2;
        return  !n ? a : b;
    }

Here is my current favorite fast fibonacci function (which happens
to be written in a functional and tail-recursive style):

   static      ULL  ff( ULL, ULL, unsigned, unsigned );
   static unsigned  lone( unsigned );

   ULL
   ffibonacci( unsigned n ){
      return  ff( 1, 0, lone( n ), n );
   }

   ULL
   ff( ULL a, ULL b, unsigned m, unsigned n ){
    ULL c = a+b;
      return
         m & n   ?  ff(          (a+c)*b, b*b+c*c,  m>>1, n )  :
         m       ?  ff( a*a+b*b, (a+c)*b,           m>>1, n )  :
         /*****/    b;
   }

   unsigned
   lone( unsigned n ){
      return  n |= n>>1,  n |= n>>2,  n |= n>>4,  n ^ n>>1;
   }

Much faster than the linear version.