Re: MISRA C

From	Ben Bacarisse <ben@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: MISRA C
Date	2026-10-05 01:22 +0100
Organization	A noiseless patient Spider
Message-ID	<87h5j19et6.fsf@bsb.me.uk> (permalink)
References	(15 earlier) <1196l3v$1b0$1@news.muc.de> <1196nn7$3upk9$1@kst.eternal-september.org> <1197piq$8k7p$1@dont-email.me> <87o6da9yyi.fsf@bsb.me.uk> <119tmoo$3vc6l$1@dont-email.me>

Show all headers | View raw

David Brown <david.brown@hesbynett.no> writes:

> On 04/10/2026 00:55, Ben Bacarisse wrote:
...
>> 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.  
>
> That surprises me.  (The rest of your post follows quite logically from this
> one point.)  Maybe I need to brush up on my computation theory here - it's
> been a while sine I studied it.

Maybe my post was not clear.  I can see why it might have been as was
assuming a model I only put at the end of my post:

> In an imaginary C with unbounded integers, you can do it with a couple
> of VLAs at the top of the function.

I should have said you need only O(m) extra numbers.  As you go on to
say, the storage for the actual numbers is significant for the actual
space complexity, but I don't think that is what people were talking
about when the were referring to "stack depth".  For one thing formal
space complexity is always relative to some model of computation --
usually Turing machines which have no stacks.

> A(m, n) can be calculated as (2 arrow[m-2] (n+3)) - 3, or using H(k, a, b)
> to mean (a arrow[k - 2] b), A(m, n) = H(m, 2, n + 3) - 3.
>
> Hyperoperations H are also defined recursively, where
>
> H(0, a, b) = b + 1	// The successor function
> H(1, a, b) = a + b	// Addition
> H(2, a, b) = a * b	// Multiplication
> H(3, a, b) = a ^ b	// Exponentiation
> H(4, a, b) = a ^ (a ^ (a ^ (a ^ ...))) with b copies
> H(5, a, b) = H(4, a, H(5, a, b - 1))
> H(n, a, b) = H(n - 1, a, H(n, a, b - 1))
>
>
> At each level, I think I can see how H(k, a, b) could be done with a number
> of nested loops where that number can be calculated from k, a and b, and
> that number gives you a size you can allocate for the loop index stack.  But
> inside the inner loop will be a call to H(k - 1, a2, b2), and each of these
> will similarly need nested loops and its own extra stack - the size of which
> will depend on k-1, a2 and b2.  (When k is small enough, you don't need that
> - it gets down to calculations that can be done directly.)  I don't see how
> you can know an upper bound for all these at the start of the H(k, a, b)
> calculation - even simplifying with the knowledge that a is 2 here.

I'm not sure this helps. H is defined in quite a similar way to A, to
you have just moved the goal posts.

> I also think disregarding the space for the numbers is perhaps "cheating"
> here.  It does not really make things more complicated either - in fact, it
> simplifies one aspect of it.  It means you are going to need at least
> O(log(A(n, m))) space to calculate A(n, m), so you are going to need to know
> A(n, m) (or an upper bound for it) before allocating space.

Sure.  I meant O(m) extra numbers.  I should have been clearer up front.

-- 
Ben.

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