Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #394710
| From | Kaz Kylheku <643-408-1753@kylheku.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Optimization of cascading recursions in "C" compilers? |
| Date | 2025-10-24 17:14 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20251024094944.64@kylheku.com> (permalink) |
| References | (3 earlier) <20251022161629.185@kylheku.com> <d5bmfktijpt62hvbdo4irgs0as8b17v3qg@4ax.com> <10dfvds$2k51h$1@dont-email.me> <20251024173549.00002111@yahoo.com> <10dg5kb$2m3c5$2@dont-email.me> |
On 2025-10-24, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> On 24.10.2025 16:35, Michael S wrote:
>> On Fri, 24 Oct 2025 15:36:58 +0200
>> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
>>
>>> On 24.10.2025 09:53, Rosario19 wrote:
>>>>
>>>>
>>>>> into the above pair of functions, or anything similar.
>>>>>
>>>>> That's not ordinary optimization of the type which improves the
>>>>> code generated for the user's algorithm; that's recognizing and
>>>>> redesigning the algorithm.
>>>>>
>>>>> The line between those is blurred, but not /that/ blurred.
>>>>
>>>> int fib1(int n){return fib_tail(0, 1, n);}
>>>>
>>>> is different from
>>>>
>>>> int fib(int n){if(n<2) return 1;return fib(n - 1) + fib(n - 2);
>>>>
>>>>
>>>> both these function calculate from the 0 1 the number result, but
>>>> fib() start to calculate from n goes dowwn until n=0, than goes up
>>>> until n=input, instead fib1() go only down for n. It seen the calls
>>>> (fib has 2 call each call... instead fib_tail() just 1), I think
>>>> fib() is O(n^2) instead fib1 is O(n).
>>>
>>> It's worse; it's O(2^N).
>>>
>>> Janis
>>>
>>
>> Actually, the number of calls in naive recursive variant = 2*FIB(N)-1.
>> So, O(1.618**n) - a little less bad than your suggestion.
>
> It's new to me that O-complexities would be written with decimals.
>
> You also don't say that 'insertion sort' is O((N^2)/2); it's O(N^2).
I think, whereas constant factors and constant terms are understood not
to matter in asymptotic complexity, the choice of exponential base in
exponential complexity does. Similarly to the choice of exponent
in the category of polynomial time: e.g. cubic is slower than quadratic.
If we have 1 < a < b then O(b^n) is a faster growth than O(a^n).
2^n doubles with every increment in n.
Whereas 1.02^n doubles --- here we can use the 'rule of 72' from
finance --- for a +36 increase in n.
If spending twice the computing time buys us only a +1 increase in
the input parameter n, versus +36, that's a big deal.
A term added to n in in 2^n wouldn't matter because 2^(n+c)
is (2^c)(2^n) translating to a constant factor. But a coefficient
on n would matter: 2^(kn) = (2^k)^n. It changes the base.
--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-09-30 17:54 +0200
Re: Optimization of cascading recursions in "C" compilers? David Brown <david.brown@hesbynett.no> - 2025-09-30 18:04 +0200
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 00:15 +0200
Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-09-30 16:12 +0000
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 00:07 +0200
Re: Optimization of cascading recursions in "C" compilers? Ben Bacarisse <ben@bsb.me.uk> - 2025-10-01 10:05 +0100
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 19:01 +0200
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-01 19:08 +0200
Re: Optimization of cascading recursions in "C" compilers? Ben Bacarisse <ben@bsb.me.uk> - 2025-10-02 00:48 +0100
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-02 05:25 +0200
Re: Optimization of cascading recursions in "C" compilers? Ben Bacarisse <ben@bsb.me.uk> - 2025-10-03 15:09 +0100
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-03 16:47 +0200
Re: Optimization of cascading recursions in "C" compilers? bart <bc@freeuk.com> - 2025-10-01 00:02 +0100
Re: Optimization of cascading recursions in "C" compilers? antispam@fricas.org (Waldek Hebisch) - 2025-10-01 01:22 +0000
Re: Optimization of cascading recursions in "C" compilers? Rosario19 <Ros@invalid.invalid> - 2025-10-23 00:37 +0200
Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-22 23:36 +0000
Re: Optimization of cascading recursions in "C" compilers? Rosario19 <Ros@invalid.invalid> - 2025-10-24 09:53 +0200
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-24 15:36 +0200
Re: Optimization of cascading recursions in "C" compilers? Michael S <already5chosen@yahoo.com> - 2025-10-24 17:35 +0300
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-24 17:22 +0200
Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-24 17:14 +0000
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-24 20:31 +0200
Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-24 23:59 +0000
Re: Optimization of cascading recursions in "C" compilers? James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-10-27 05:48 -0400
Re: Optimization of cascading recursions in "C" compilers? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2025-10-27 12:52 +0100
Re: Optimization of cascading recursions in "C" compilers? James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-10-27 14:41 -0400
Re: Optimization of cascading recursions in "C" compilers? Michael S <already5chosen@yahoo.com> - 2025-10-27 22:33 +0200
Re: Optimization of cascading recursions in "C" compilers? James Kuyper <jameskuyper@alumni.caltech.edu> - 2025-10-27 16:52 -0400
Re: Optimization of cascading recursions in "C" compilers? Kaz Kylheku <643-408-1753@kylheku.com> - 2025-10-27 21:03 +0000
Re: Optimization of cascading recursions in "C" compilers? antispam@fricas.org (Waldek Hebisch) - 2025-10-28 01:58 +0000
csiph-web