Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #121267
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: constexpr is really very smart! |
| Date | 2024-12-20 02:17 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <20241220021703.00003e9e@yahoo.com> (permalink) |
| References | (1 earlier) <20241216112808.00003f74@yahoo.com> <86jzbyghdw.fsf@linuxsc.com> <20241218013342.0000518a@yahoo.com> <20241218135131.00000006@yahoo.com> <86zfksf4lb.fsf@linuxsc.com> |
On Thu, 19 Dec 2024 00:40:32 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 18 Dec 2024 01:33:42 +0200
> > Michael S <already5chosen@yahoo.com> wrote:
> >
> >> I am pretty sure that better variant exists, but for tonight it's
> >> enough.
> >
> > Morning fibs.
> >
> > Recursive:
> >
> > struct pair_t {
> > long long a,b;
> > };
> >
> > // return .a=fib(n), .b=fib(n+1)
> > static struct pair_t fib2(long n)
> > {
> > if (n <= 0) {
> > struct pair_t ret = { .a = 0, .b = n==0 ? 1 : 0 };
> > return ret;
> > }
> > // for n > 0
> > // fib(n*2) = (fib(n-1)+fib(n+1))*fib(n)
> > // fib(n*2+1) = fib(n)*fib(n)+fib(n+1)*fib(n+1)
> > long m = (n-1) >> 1;
> > struct pair_t ret = fib2(m);
> > long long a = ret.a, b = ret.b;
> > long long c = a + b;
> > if ((n & 1)==0) { // (m,m+1) => ((m+1)*2,(m+1)*2*2+1)
> > ret.a = (a + c)*b;
> > ret.b = b*b + c*c;
> > } else { // (m,m+1) => (m*2+1,(m+1)*2)
> > ret.a = a*a + b*b;
> > ret.b = (a + c)*b;
> > }
> > return ret;
> > }
> >
> > static long long fib(long n)
> > {
> > struct pair_t x = fib2(n-1);
> > return x.b;
> > }
>
> I may have inadvertently misled you. Here is a simple linear
> formulation that uses recursion:
>
> typedef unsigned long long NN;
>
> static NN fibonacci_3( NN, NN, unsigned );
>
> NN
> fibonacci( unsigned n ){
> return fibonacci_3( 1, 0, n );
> }
>
> NN
> fibonacci_3( NN a, NN b, unsigned n ){
> return n == 0 ? b : fibonacci_3( b, a+b, n-1 );
> }
>
> Can you apply this idea to your logarithmic scheme?
>
>
Not really. But I can cheat.
Below is slightly modified iterative algorithm coded as recursion.
static
long long fib_3(long long a, long long b, unsigned long rev_n) {
if (rev_n == 1)
return b;
long long c = a + b;
if ((rev_n & 1) == 0)
return fib_3(a*a+b*b, (a+c)*b, rev_n/2);
else
return fib_3((a+c)*b, b*b+c*c, rev_n/2);
}
static
long long fib_bitrev(unsigned long a, unsigned long b) {
return a==1 ? fib_3(0, 1, b) : fib_bitrev( a / 2, b * 2 + a % 2);
}
long long fib(long n) {
return n <= 0 ? 0 : fib_bitrev(n, 1);
}
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-15 20:20 +0000
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 11:28 +0200
Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 11:18 +0100
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 13:23 +0200
Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 13:43 +0100
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-17 11:08 +0200
Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-17 11:10 +0100
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 03:26 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:39 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 07:42 -0800
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-17 12:54 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 01:33 +0200
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 13:51 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:40 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-20 02:17 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:59 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:07 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:25 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 17:47 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-24 05:21 -0800
Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 11:05 +0200
Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 13:33 +0200
Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:54 -0800
Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:42 -0800
Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-19 19:14 +0000
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 09:45 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 22:00 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:57 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-19 23:45 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:31 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:14 +0200
Re: constexpr is really very smart! James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-12-21 17:55 -0500
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 02:22 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:33 -0800
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 00:05 +0200
Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 17:17 -0800
Re: constexpr is really very smart! Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-12-17 12:20 -0800
Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-18 04:45 +0000
Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:17 +0200
csiph-web