Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #402705

Re: MISRA C

Show all headers | View raw

antispam@fricas.org (Waldek Hebisch) writes:

> Ben Bacarisse <ben@bsb.me.uk> wrote:
>> Sorry I'm jumping in here.  I don't read Usenet much these days but this
>> got me going.
>> 
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> You can implement the Ackermann function without explicit recursion, just
>>> using a single loop and with allocated stacks or lists to hold the progress.
>>> But you /cannot/ do so with a single allocation at the start.   If you are
>>> asked to calculate A(m, n), you cannot calculate an upper bound on the stack
>>> size you need without calculating the function.
>> 
>> Hmm...  This is likely to confuse people.  You can calculate A(m, n)
>> using O(m) extra space.  You can pre-allocate the space you need before
>> starting the calculation.  (Aside: this disregards the space needed to
>> store the numbers.  A(m, n) grows so large that you need extra space
>> just to store the integers, but that complicates the discussion and I
>> think everyone has been ignoring it in this thread anyway.)
>
> Not everone.  C does not have unbounded integers, so in C using
> signed numbers computation will very quickly lead to overflow.
> On can handle non-overflowing cases by very simple iterative code.
> Even in language with unbounded integers in practice Ackermann
> very quickly will overflow.  So in practice Ackermann is easily
> computable, you either get overflow or comptational cost is
> related to size of the answer.
>
> In theory, as long as you have two unbounded numeric variables and
> a reasonable fixed number of bounded variables you can emultate
> single tape Turing machine, so you can compute anything computable.

Sure.  I have made a mess of what I was saying as it's not really about
formal complexity at all but about an analysis of possible algorithms as
your example makes explicit.

Maybe no misconception need to be corrected in the thread.  I just got
the idea that some people thought there was no way to know how deep a
stack (or how large a temporary array of [big]numbers) would be needed
before computing A(m, n).

...
>> A carefully written recursive version will also use only O(m) stack, but
>> here we get into problems of definition.  Given that there is an
>> iterative version that needs only O(m) extra storage there is obviously
>> a trivial recursive version of that function that, say, just pointlessly
>> calls itself once!
>
> AFAIK when you allocate memory at the start some functional folks
> will still call it iterative.  After all you can just use one
> vector valued variables plus possibly a fixed number of temporaries.
> Only when you really do allocation on the stack and access the
> allocated values in stack-like manner it is considerd trurly
> recursive.  AFAICS the following has recursion depth of m and
> uses fixed number of variables per recursion level:
>
> bigint A(bigint m, bigint n) {
>     if (m == 0) {
>         return n + 1;
>     }
>     bigint res = 1;
>     for(bigint l = 0; l <= n; l++) {
>         tmp = A(m - 1, tmp);

Surely s/tmp/res/g?

>     }
>     return res;
> }
>
> where bigint is appropriate type for unbounded integers.

-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

MISRA C (was: buckle-up ....) Alan Mackenzie <acm@muc.de> - 2026-09-25 10:01 +0000
  Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-25 14:52 +0200
    Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 13:48 +0000
      Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-25 16:39 +0200
        Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 15:10 +0000
          Re: MISRA C bart <bc@freeuk.com> - 2026-09-25 16:57 +0100
          Re: MISRA C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-09-25 11:42 -0700
            Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 20:21 +0000
              Re: MISRA C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-09-25 14:05 -0700
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-26 08:43 +0200
                Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-26 17:55 +0000
                Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-03 23:55 +0100
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-04 16:10 +0200
                Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-05 01:22 +0100
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-05 07:59 +0200
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-05 01:23 -0700
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-05 01:24 -0700
                Re: MISRA C antispam@fricas.org (Waldek Hebisch) - 2026-10-05 09:02 +0000
                Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-05 12:07 +0200
                Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-05 15:29 +0100
                Re: MISRA C antispam@fricas.org (Waldek Hebisch) - 2026-10-05 20:29 +0000
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 22:13 -0700
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 22:14 -0700
          Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-09-27 10:52 -0700
          Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 13:08 +0200
            Re: MISRA C bart <bc@freeuk.com> - 2026-09-28 13:07 +0100
            Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-28 14:08 +0200
              Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 14:28 +0200
            Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-28 12:17 +0000
              Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 14:40 +0200
          Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-30 10:21 -0700
            Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-30 19:57 +0000
              Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-30 13:09 -0700
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-01 08:47 +0200
                Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-01 15:18 -0700
      Re: MISRA C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-27 04:58 +0800
  Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-25 17:02 +0200
  Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-26 15:37 -0700

csiph-web