Re: MISRA C

From	David Brown <david.brown@hesbynett.no>
Newsgroups	comp.lang.c
Subject	Re: MISRA C
Date	2026-10-04 16:10 +0200
Organization	A noiseless patient Spider
Message-ID	<119tmoo$3vc6l$1@dont-email.me> (permalink)
References	(14 earlier) <1196fb8$3rdj2$1@kst.eternal-september.org> <1196l3v$1b0$1@news.muc.de> <1196nn7$3upk9$1@kst.eternal-september.org> <1197piq$8k7p$1@dont-email.me> <87o6da9yyi.fsf@bsb.me.uk>

Show all headers | View raw

On 04/10/2026 00:55, Ben Bacarisse wrote:
> Sorry I'm jumping in here.  I don't read Usenet much these days but this
> got me going.
> 

It is always good to hear from you - c.l.c. was richer when you posted 
more often.

> 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.

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 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.


> 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.)
> 
> 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!
> 
>> But with malloc() and realloc(), you are good to go!
> 
> In an imaginary C with unbounded integers, you can do it with a couple
> of VLAs at the top of the function.
>

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