Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Safety of casting from 'long' to 'int' Date: Sun, 10 May 2026 21:49:50 -0700 Organization: A noiseless patient Spider Lines: 109 Message-ID: <86a4u6r1n5.fsf@linuxsc.com> References: <10su8cn$am9i$1@dont-email.me> <10tie4h$1l93l$1@dont-email.me> <10tiu79$obc$1@reader1.panix.com> <86mry8so39.fsf@linuxsc.com> <10to4go$e9f$1@reader1.panix.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Mon, 11 May 2026 04:49:51 +0000 (UTC) Injection-Info: dont-email.me; logging-data="891567"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19cH/LoqcMcQS++TcOtdrq7RzNRbfzPbiE="; posting-host="e12ff559fd79fb3307443db8d47ea871" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:09bvD5kFht+Gpb4KIVkmVxM2Fp4= sha1:CKl4xiO2eqlHVfqnxGx6w6s/l24= sha256:zUwG0IBFlqMpZce3CJaaLVoE8uUSkih0wgXAUnNg50g= sha1:iEVpuoPEUEdSlt9jNUSA6w96dXA= Xref: csiph.com comp.lang.c:398704 cross@spitfire.i.gajendra.net (Dan Cross) writes: > In article <86mry8so39.fsf@linuxsc.com>, > Tim Rentsch wrote: > >> cross@spitfire.i.gajendra.net (Dan Cross) writes: >> >>> [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... >> >> [snip] >> >>> (Origin 0, not 1.) >> >> fibonacci(0) is 0. There is no other. > > You are correct, and I was incorrect stating that Fib(n) is > undefined for n<0. [...] No worries, I just wanted to stick to the usual formulation. >> [snip] >> 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. > > Very nice. 64-bit `unsigned long long` overflows for n>93, so I > question how much it matters in practice, though; surely if > calling this frequently you simply cache it in some kind of > table? Depends on the cost of a cache miss. Because the computational version is very fast, I tend to prefer it over a lookup table with its higher variability. > I wondered how this compared to Binet's Formula, using floating > point: > > ``` > unsigned long long > binet_fib(unsigned int n) > { > const long double sqrt5 = sqrtl(5.); > > long double fn = > (powl(1. + sqrt5, n) - powl(1. - sqrt5, n)) / > (powl(2., n) * sqrt5); > > return llroundl(fn); > } > ``` > > Sadly, my quick test suggests accuracy suffers (presumably due > to floating point) for the larger representable values in the > sequence; specifically, n>90. As a result I didn't bother > attempting to benchmark it. Yes, that is the perennial problem with floating point. Also it's hard to scale up floating point, and fairly easy with integers. Here is code that works up to n = 186: typedef __uint128_t U128; static U128 qff( U128, U128, unsigned, unsigned ); static unsigned lone( unsigned ); U128 qfibonacci( unsigned n ){ return qff( 1, 0, lone( n ), n ); } U128 qff( U128 a, U128 b, unsigned m, unsigned n ){ U128 c = a+b; return m & n ? qff( (a+c)*b, b*b+c*c, m>>1, n ) : m ? qff( 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; }