Programming challenge

Discussion in 'C Programming' started by annalissa, Dec 14, 2009.

  1. annalissa

    annalissa Guest

    annalissa, Dec 14, 2009
    #1
    1. Advertising

  2. annalissa

    Dann Corbit Guest

    In article <hg68kr$8c5$>, says...
    >
    > Hi all,
    >
    > see this article,
    > http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
    >
    > my question is can this be done in C ?


    You can perform factorial calculation without recursion or iteration in
    any language.

    The best answer is table lookup. You can also use Sterling's
    approximation. Anything that expands in size at factorial rate will
    result in a small table, no matter how precise your number format is.

    There are no nameless functions in C, but you could probably do some
    lame preprocessor trick or something of that nature if you want to look
    especially clever.

    Any of the functions used to calculate the gamma function can also be
    used, since the factorial function is just the gamma function at
    integral points shifted by 1.
     
    Dann Corbit, Dec 14, 2009
    #2
    1. Advertising

  3. On 12/14/2009 12:54 PM, annalissa wrote:
    > see this article,
    > http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
    >
    > my question is can this be done in C ?


    I'm not a LISP guy, but that non-recursive solution reeks of recursion,
    even if it's not strictly recursive. (It looks like, "Let's recursively
    produce a series of lambda functions that we multiply together to
    produce a factorial"--but I'm not a LISP guy so I could be totally
    wrong.) Or to put it another way, you're going to be looping through
    those values one way or another, whether you like it or not.

    My short painful answer would be: write a C program that interprets LISP
    and feed it the LISP program. So, yes, it can be done in C. :) But can
    the same structure be used in the C language? No, not really--unless
    there's some clever solution I'm overlooking. Can the preprocessor be
    abused into generating the factorial code?

    -Beej
     
    Beej Jorgensen, Dec 14, 2009
    #3
  4. annalissa <> writes:

    > see this article,
    > http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219


    That pages does not have a "factorial without recursion or iteration"
    function on it. It links to a page that does have one -- by using
    a fixed point combinator.

    > my question is can this be done in C ?


    Not directly, but the answer to all such questions is, at some level,
    always "yes". You could build a combinator reduction engine in C and
    you'd then be doing the same in C if you fed in the right combinator
    form (in fact, it is surprisingly little code).

    If, however, by "this" you mean write almost any function but without
    using iteration or recursion then the answer is no.

    [I have to add that serious pre-processor abuse might be able to
    come close, though I suspect some of the worst tricks would probably
    count as recursion.]

    --
    Ben.
     
    Ben Bacarisse, Dec 14, 2009
    #4
  5. Beej Jorgensen writes:
    > On 12/14/2009 12:54 PM, annalissa wrote:
    >> http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
    >>
    >> my question is can this be done in C ?

    >
    > I'm not a LISP guy, but that non-recursive solution reeks of recursion,
    > even if it's not strictly recursive. (It looks like, "Let's recursively
    > produce a series of lambda functions that we multiply together to
    > produce a factorial"--but I'm not a LISP guy so I could be totally
    > wrong.)


    That's right. Maybe a Python solution (without Python lambda
    expressions) will look more readable to C programmers:

    def U(f):
    return f(f)

    def fact_nr(f):
    def step(n):
    return (1 if n == 0 else n * f(f)(n - 1))
    return step

    print U(fact_nr)(3), U(fact_nr)(5) # prints 6 120

    > My short painful answer would be: write a C program that interprets LISP
    > and feed it the LISP program. So, yes, it can be done in C. :) But can
    > the same structure be used in the C language?


    That use of functions, no: No functions inside functions, and local
    variables fact_nr:f and step:n) die when a function exits.

    The same program structure more grossly, yes: You can create structs
    representing a called function (i.e. a closure), a call to a function
    (with a function pointer and maybe arguments), etc, and then some
    machinery to call that kind of function -- but you already said that,
    "write a C program which interprets LISP":)

    > No, not really--unless
    > there's some clever solution I'm overlooking. Can the preprocessor be
    > abused into generating the factorial code?


    Nope. It's explicitly defined to not do recursive expansion. You can
    write preprocessor macros with the same structure as a recursive call or
    iteration, but by spelling out each round/call for as many rounds as you
    are intersted in supporting.

    /* Factorial macro, works for arguments 0..5 */
    #define FACTORIAL(n) (ASSERTZ((n) <= 5) + F5(n))
    #define F5(n) ((n) <= 1 ? 1 : (n) * F4((n)-1))
    #define F4(n) ((n) <= 1 ? 1 : (n) * F3((n)-1))
    #define F3(n) ((n) <= 1 ? 1 : (n) * F2((n)-1))
    #define F2(n) ((n) <= 1 ? 1 : (n) * F1((n)-1))
    #define F1(n) 1

    /* Return 0, but try to force a compile error if !c */
    #define ASSERTZ(c) (sizeof(struct { \
    int Assert1_[(c) ? 9 : -9]; int Assert2_: (c) ? 9 : -9; }) && 0)


    Watch out for "recursive" expansion expanding the previous round's macro
    several times though - that can quickly give you a gigabyte-sized
    macroexpansion. In that case, you'd have to write a macro which expands
    to a set of declarations which declares the local variables for each
    iteration/recursive call - and hope the compiler optimizes all that
    away. Or expand to an enum declaration, if you can keep the locals in
    the range of INT_MIN..INT_MAX.

    Of course, all of this as well as the original example is vast overkill
    for factorial, but it illustrates the point.

    --
    Hallvard
     
    Hallvard B Furuseth, Dec 14, 2009
    #5
  6. annalissa

    Eric Sosman Guest

    On 12/14/2009 4:26 PM, Dann Corbit wrote:
    > In article<hg68kr$8c5$>, says...
    >>
    >> Hi all,
    >>
    >> see this article,
    >> http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
    >>
    >> my question is can this be done in C ?

    >
    > You can perform factorial calculation without recursion or iteration in
    > any language.
    >
    > The best answer is table lookup. You can also use Sterling's
    > approximation.[...]


    Just in case someone wants to look it up: "Stirling," with
    two ayes and no ease.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Dec 14, 2009
    #6
  7. I wrote:
    > Beej Jorgensen writes:
    >> Can the preprocessor be
    >> abused into generating the factorial code?

    >
    > Nope. It's explicitly defined to not do recursive expansion.


    ....and to detect tricks like calling macros indirectly in order to try
    for recursion. (So the halting problem is not a problem for the compiler.)

    > You can
    > write preprocessor macros with the same structure as a recursive call or
    > iteration, but by spelling out each round/call for as many rounds as you
    > are intersted in supporting.
    >
    > (...example snipped...)
    > Watch out for "recursive" expansion expanding the previous round's macro
    > several times though - that can quickly give you a gigabyte-sized
    > macroexpansion. In that case, you'd have to write a macro which expands
    > to a set of declarations which declares the local variables for each
    > iteration/recursive call - and hope the compiler optimizes all that
    > away. Or expand to an enum declaration, if you can keep the locals in
    > the range of INT_MIN..INT_MAX.


    I mean, to eliminate exponential growth of the macroexpansion. Instead
    of expanding the macro twice to compute the same value, expand it once
    and stuff the result into a variable or enum constant.

    > Of course, all of this as well as the original example is vast overkill
    > for factorial, but it illustrates the point.


    --
    Hallvard
     
    Hallvard B Furuseth, Dec 14, 2009
    #7
  8. annalissa

    Gene Guest

    On Dec 14, 3:54 pm, annalissa <> wrote:
    > Hi all,
    >
    > see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...
    >
    > my question is can this be done in C ?


    On Dec 14, 3:54 pm, annalissa <> wrote:
    > Hi all,
    >
    > see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...
    >
    > my question is can this be done in C ?


    Of course it can. As is often the case with C, you merely need to pay
    attention to a few more details to get the job done:

    #include <stdio.h>
    #include <stdlib.h>

    // (define (fact-nr f)
    // (lambda (n) (if (zero? n) 1
    // (* n ((f f) (- n 1))))))

    // activation record for fact
    typedef struct fact_s {
    struct lambda_s *(*code)(struct fact_s *);
    struct fact_s *f;
    } FACT;

    // activation record for lambda
    typedef struct lambda_s {
    int (*code) (struct lambda_s *);
    struct fact_s *env;
    int n;
    } LAMBDA;

    // forward declarations
    int lambda_code(LAMBDA *env);
    LAMBDA *fact_code(FACT *env);

    // return a fresh lambda activation
    LAMBDA *new_lambda(FACT *env)
    {
    LAMBDA *lambda = malloc(sizeof *lambda);
    lambda->code = lambda_code;
    lambda->env = env;
    return lambda;
    }

    // call a lambda with given argument n
    int call_lambda(LAMBDA *lambda, int n)
    {
    lambda->n = n;
    return lambda->code(lambda);
    }

    // return a fresh fact activation
    FACT *new_fact(void)
    {
    FACT *fact = malloc(sizeof *fact);
    fact->code = fact_code;
    return fact;
    }

    // call a fact with given argument f
    LAMBDA *call_fact(FACT *fact, FACT *f)
    {
    fact->f = f;
    fact->code(fact);
    }

    // code for lambda activation
    int lambda_code(LAMBDA *env)
    {
    return (env->n == 0) ? 1 :
    env->n * call_lambda(call_fact(env->env->f,
    env->env->f),
    env->n - 1);
    }

    // code for a fact activation
    LAMBDA *fact_code(FACT *env)
    {
    return new_lambda(env);
    }

    // U-combinator for fact activations
    LAMBDA *U(FACT *f)
    {
    return call_fact(f, f);
    }

    // try it out
    int main(void)
    {
    FACT *fact = new_fact();
    LAMBDA *lambda = U(fact);
    printf("fact(3) ==> %d\n", call_lambda(lambda, 3));
    printf("fact(5) ==> %d\n", call_lambda(lambda, 5));
    return 0;
    }

    C:\>a.exe
    fact(3) ==> 6
    fact(5) ==> 120
     
    Gene, Dec 17, 2009
    #8
  9. annalissa

    Gene Guest

    On Dec 16, 11:33 pm, Gene <> wrote:
    > On Dec 14, 3:54 pm, annalissa <> wrote:
    >
    > > Hi all,

    >
    > > see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...

    >
    > > my question is can this be done in C ?

    >
    > On Dec 14, 3:54 pm, annalissa <> wrote:
    >
    > > Hi all,

    >
    > > see this article,http://pramode.net/2006/01/09/factorial-without-recursion-or-iteratio...

    >
    > > my question is can this be done in C ?

    >
    > Of course it can. As is often the case with C, you merely need to pay
    > attention to a few more details to get the job done:
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > // (define (fact-nr f)
    > //   (lambda (n) (if (zero? n) 1
    > //                   (* n ((f f) (- n 1))))))
    >
    > // activation record for fact
    > typedef struct fact_s {
    >   struct lambda_s *(*code)(struct fact_s *);
    >   struct fact_s *f;
    >
    > } FACT;
    >


    Rest of code deleted...

    If you get the previous post, then try this "optimization," which
    notes that no activation record is required for the factorial
    function:


    #include <stdio.h>
    #include <stdlib.h>

    // with no free variables, fact is just a function
    typedef struct lambda_s *FACT();

    // the inner lambda needs an activation record (sort of)
    typedef struct lambda_s {
    int (*code) (struct lambda_s *);
    FACT *f;
    int n;
    } LAMBDA;

    int lambda_code(LAMBDA *env);

    // fact returns a lambda bound to f
    LAMBDA *fact(FACT *f)
    {
    LAMBDA *lambda = malloc(sizeof *lambda);
    lambda->code = lambda_code;
    lambda->f = f;
    return lambda;
    }

    int call_lambda(LAMBDA *lambda, int n)
    {
    lambda->n = n;
    return lambda->code(lambda);
    }

    int lambda_code(LAMBDA *env)
    {
    return (env->n == 0) ? 1 :
    env->n * call_lambda(env->f(env->f), env->n - 1);
    }

    // U combinator for type FACT
    LAMBDA *U(FACT *f)
    {
    return f(f);
    }

    int main(void)
    {
    LAMBDA *lambda = U(fact);
    printf("fact(3) ==> %d\n", call_lambda(lambda, 3));
    printf("fact(5) ==> %d\n", call_lambda(lambda, 5));
    return 0;
    }
     
    Gene, Dec 17, 2009
    #9
  10. On 12/16/2009 08:33 PM, Gene wrote:
    > Of course it can. As is often the case with C, you merely need to pay
    > attention to a few more details to get the job done:
    >
    > #include <stdio.h>
    > [... snip ...]


    Terrifyingly awesome.

    -Beej
     
    Beej Jorgensen, Dec 17, 2009
    #10
  11. annalissa

    Phil Carmody Guest

    Beej Jorgensen <> writes:
    > On 12/16/2009 08:33 PM, Gene wrote:
    >> Of course it can. As is often the case with C, you merely need to pay
    >> attention to a few more details to get the job done:
    >>
    >> #include <stdio.h>
    >> [... snip ...]

    >
    > Terrifyingly awesome.


    But lambda_code calls code which calls lambda_code, so it's
    just recursion via structures containing function pointers.
    I thought the purpose was to avoid recursion? (And be completely
    pointless.)

    Use lisp for lisp, and C for C, that's what I say.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Dec 17, 2009
    #11
  12. Gene <> kirjoitti 17.12.2009:
    > // activation record for fact
    > // activation record for lambda


    I'm pretty sure those were actually closures, not activation records. A more
    common synonym for the latter is "stack frame", but an activation record can
    also reside on the heap.

    Impressive, still. :)

    --
    Mr. Antti-Juhani Kaijanaho, Jyvaskyla, Finland
     
    Antti-Juhani Kaijanaho, Dec 17, 2009
    #12
  13. annalissa

    Stefan Ram Guest

    annalissa <> writes:
    >my question is can this be done in C ?


    I have noticed this thread just 5 minutes ago:
    Yes, you can remove direct recursion using
    a Y-combinator like approach in C:

    #include <stdio.h>

    int g( int const i, int( *h )() )
    { return i ? i * h( i - 1, h ) : 1; }

    /* This is not the Y combinator,
    just a C function called "Y". */
    int Y( int const i, int( *g )() )
    { return g( i, g ); }

    int factorial( int const i ){ return Y( i, g ); }

    int main( void ){ printf( "%d\n", factorial( 5 )); }

    /* prints
    120
    */
     
    Stefan Ram, Dec 17, 2009
    #13
  14. -berlin.de (Stefan Ram) writes:

    > annalissa <> writes:
    >>my question is can this be done in C ?

    >
    > I have noticed this thread just 5 minutes ago:
    > Yes, you can remove direct recursion using
    > a Y-combinator like approach in C:
    >
    > #include <stdio.h>
    >
    > int g( int const i, int( *h )() )
    > { return i ? i * h( i - 1, h ) : 1; }
    >
    > /* This is not the Y combinator,
    > just a C function called "Y". */
    > int Y( int const i, int( *g )() )
    > { return g( i, g ); }
    >
    > int factorial( int const i ){ return Y( i, g ); }
    >
    > int main( void ){ printf( "%d\n", factorial( 5 )); }


    Y is not needed; it seems only there to complicate matters. If you
    define

    int factorial( int const i ){ return g( i, g ); }

    then the code is a little clearer and it becomes clear that g calls g.
    OK, it's called h at the time, but it is still g that is being called!

    --
    Ben.
     
    Ben Bacarisse, Dec 17, 2009
    #14
  15. annalissa

    Stefan Ram Guest

    (Richard Tobin) writes:
    >>my question is can this be done in C ?

    >So I conclude that it is not possible to solve the problem as
    >constrained above in C.


    I am not sure to which problem the word »this« as quoted
    above refers to. Maybe someone can give a wording of the
    problem, so that it is definitely defined about which
    problem we are actually talking.

    PS: In my preceding post, I inadvertently seem to have
    deleted the reference header line as this sometime happen
    when I edit my posts. Sorry, I will try to keep this line
    intact in the future.
     
    Stefan Ram, Dec 18, 2009
    #15
  16. In article <hg68kr$8c5$>, annalissa <> wrote:
    >see this article,
    >http://pramode.net/2006/01/09/facto...n-or-iteration-or-how-tc-can-be-fun/#more-219
    >
    >my question is can this be done in C ?


    Sorry I'm coming in to this late.

    If you want to calculate N factorial by the natural method of
    multiplying tigether the numbers from 1 to N, you're obviously going
    to be doing a variable number of multiplications. If we are willing
    to bound N (which is implicit, for a given C implementation, in any
    solution using fixed-size integers), we can write a program with no
    iteration or recursion simply by enumerating the possible values of N:

    int fact=1;
    if(N == 1)
    return fact;
    f *= 2;
    if(N == 2)
    return fact;
    ...

    If we wish to write as if N is unbounded, we must have some construct
    that provides an unbounded variable number of operations. Either we
    will use this operation explicitly, or it will be concealed in the C
    library. As far as I can see, the only operations of this nature in C
    are the looping constructs, goto, and recursion. I cannot see any
    standard library function that can be persuaded to do the required
    multiplications.

    (It might be possible to somehow set up an array in such a way that
    calling, say, qsort on it would do something isomorphic to multiplication,
    but we would then have the problem of setting up the array.)

    Of course you could write a library that implemented, say, combinator
    reduction, but that just moves the problem into your library.

    So I conclude that it is not possible to solve the problem as
    constrained above in C.

    -- Richard

    --
    Please remember to mention me / in tapes you leave behind.
     
    Richard Tobin, Dec 18, 2009
    #16
  17. annalissa

    janus Guest

    Stefan,

    I understand the the flow of your code but not the "spirit" of it.
    Could you explain it a little bit?

    Regards,
    Janus
    On Dec 17, 6:23 pm, -berlin.de (Stefan Ram) wrote:
    > annalissa <> writes:
    > >my question is can this be done in C ?

    >
    >   I have noticed this thread just 5 minutes ago:
    >   Yes, you can remove direct recursion using
    >   a Y-combinator like approach in C:
    >
    > #include <stdio.h>
    >
    > int g( int const i, int( *h )() )
    > { return i ? i * h( i - 1, h ) : 1; }
    >
    > /* This is not the Y combinator,
    > just a C function called "Y". */
    > int Y( int const i, int( *g )() )
    > { return g( i, g ); }
    >
    > int factorial( int const i ){ return Y( i, g ); }
    >
    > int main( void ){ printf( "%d\n", factorial( 5 )); }
    >
    >   /* prints
    > 120
    >   */
     
    janus, Dec 18, 2009
    #17
  18. annalissa

    Gene Guest

    On Dec 17, 12:42 pm, Antti-Juhani Kaijanaho <antti-
    > wrote:
    > Gene <> kirjoitti 17.12.2009:
    >
    > > // activation record for fact
    > > // activation record for lambda

    >
    > I'm pretty sure those were actually closures, not activation records.  A more
    > common synonym for the latter is "stack frame", but an activation record can
    > also reside on the heap.
    >
    > Impressive, still. :)
    >
    > --
    > Mr. Antti-Juhani Kaijanaho, Jyvaskyla, Finland


    It's a fine point. You could call them closures, but a closure does
    not normally include space for yet-to-be-bound arguments (represented
    internally as Boehm number references or similar). The structures used
    in this code do include argument space. So I called them activation
    recordes.
     
    Gene, Dec 18, 2009
    #18
  19. annalissa

    Gene Guest

    On Dec 17, 2:46 am, Phil Carmody <>
    wrote:
    > Beej Jorgensen <> writes:
    > > On 12/16/2009 08:33 PM, Gene wrote:
    > >> Of course it can. As is often the case with C, you merely need to pay
    > >> attention to a few more details to get the job done:

    >
    > >> #include <stdio.h>
    > >> [... snip ...]

    >
    > > Terrifyingly awesome.

    >
    > But lambda_code calls code which calls lambda_code, so it's
    > just recursion via structures containing function pointers.
    > I thought the purpose was to avoid recursion? (And be completely
    > pointless.)
    >
    > Use lisp for lisp, and C for C, that's what I say.
    >


    Ta da! Yes. No surprise. This is one of the points of the
    exercise. The lisp version is also "just recursion via structures
    containing function pointers." You just don't get to see much of the
    action...
     
    Gene, Dec 18, 2009
    #19
  20. annalissa

    Stefan Ram Guest

    janus <> writes:
    >I understand the the flow of your code but not the "spirit" of it.
    >Could you explain it a little bit?


    >>#include <stdio.h>
    >>int g( int const i, int( *h )() )
    >>{ return i ? i * h( i - 1, h ) : 1; }


    I do not exactly understand »spirit«, so I just talk a bit:

    Above, a function »g« is defined that is not statically recursive,
    that is, it does not contain its own name in its body. Since I did
    not know the precise wording of the »challenge« in this thread,
    I can not claim that this is a solution to the challenge. It
    was posted in the spirit of »If this was the challenge, then
    its ok, otherwise: sorry, and just ignore it.«

    However, many functions in C are latently recursive, that
    is, they might call themselves directly or indirectly even
    if they do not contain their own name. This is nearly always
    possible as soon as a functions g calls another function h,
    because h might call other functions, and one of them might
    possibly call g again.

    (When talking about »recursive functions in C«, we first
    need to define this term »recursive function in C«. I am not
    aware of a single definition yet that comes to my mind now.)

    »g« surely is latently recursive, because it even has a
    parameter that might be »g« itself (»&g« in older C
    dialects). But this does not have to be so. It is just a
    possibility.

    >>/* This is not the Y combinator,
    >>just a C function called "Y". */
    >>int Y( int const i, int( *g )() )
    >>{ return g( i, g ); }


    This Y was intended to be a »meta function«. That is, it takes
    a function g (ignoring the other parameter i for a moment) and
    then behaves as another function Yg, which depends on g:

    Y: g :--> Yg

    . And Yg happens to be the factorial.

    >>int factorial( int const i ){ return Y( i, g ); }


    The argument of the call also has to be passed through,
    which is why »i« also appears above. This shows that I
    cheated a little bit, because I do not actually generate a
    »first-class function« Yg. For example, my function Yg could
    not be passed as a function parameter to another function,
    it has no specific address (»&Yg« in older C dialects).
    But my definition was sufficient for the task at hand.

    Thus, I have a function g that is not statically recursive,
    and a transform functions Y that transforms a function into
    another function. Until now both definitions are completely
    independent. Then I apply Y to g to get the factorial, but
    Y could also be applied to other int-functions to get other
    transformed functions and g could also be used in other ways
    than be the argument of Y.

    >>int main( void ){ printf( "%d\n", factorial( 5 )); }
     
    Stefan Ram, Dec 18, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Samuel
    Replies:
    6
    Views:
    338
    Micah Cowan
    Sep 27, 2003
  2. Sara Khalatbari
    Replies:
    1
    Views:
    297
    Peter Hansen
    May 10, 2005
  3. Replies:
    2
    Views:
    357
  4. Replies:
    0
    Views:
    286
  5. Replies:
    0
    Views:
    252
Loading...

Share This Page