Programmig Newbie....where to start?

Discussion in 'C Programming' started by Kohtro, May 30, 2014.

  1. Depends what you mean. I don't know Haskell so I've got to guess, but it looks like
    the algorithm does a look up as a special case for 1 and 2, then does addition
    to calculate the rest, by using the "tail recursion" optimisation.

    In C you can express it a repeated addition, or recursively, but you can't easily
    express that the definition is both recursive and implementable by repeated addition.
    You can use big numbers in C, but not tidily. I don't know if Haskell allows you
    to express that for many uses of the function, little integers will suffice.
    We can easily enough get an array of Fibonnaci numbers in C. but it's much more
    difficult to get both the array of numbers and the Nth number without using
    N slots of memory.

    So I'd say, yes, Haskell can express ideas that C can't. It can give a single interface to
    an algorithm whilst C can only give one interface (unless you write highly complex
    and non-idiomatic C).
    Malcolm McLean, Jun 2, 2014
    1. Advertisements

  2. Not as far as I can see. In this question he has kept my wording, so he
    is asking about expressing an algorithm, rather than writing a program.
    Smiley noted, but someone might not know what you mean by that.
    I did in my reply, using both meanings: a program that can be written
    in C, and an algorithm that can't be expressed in C.
    Ben Bacarisse, Jun 3, 2014
    1. Advertisements

  3. I can't say for sure, but I think not. Many years ago I tried to do
    just that, but I decided that it did not really express the same thing,
    simply because of all the mess. However, I can't say for sure. Any
    takers? I'd love to see a natty version of this in C.
    Yes, I consider that cheating. The point is about expressing an
    algorithm, rather than writing a program.
    Ben Bacarisse, Jun 3, 2014
  4. Yes, most definitely. It's a judgement call. Well, more than one in
    fact, because first you have to say when the word "express" has lost
    it's meaning. Is there now so much machinery and detail that the ideas
    are lost? Secondly, you have to make a judgement about how much is
    algorithm and how much is implementation.

    This code works by applying a function to a list of pairs, and that list
    is made from two others, which happen to the fib sequence and the fib
    offset by one. These seem to me to be the keys parts that are
    "algorithm". The fact that Haskell needs a technical dance (uncurry
    (+)) two express the pair-adding function is not, to my mind, intrinsic
    to the algorithm. If it were, the task would be much harder.
    At some level, yes, but this defines a list not a function. To use it
    one would access an element (fib!!10000) or do other list-like things to
    it. For that reason, a C expression of the method should be as
    list or array-like as possible. I'm not sure how close you can get with
    that aspect.
    It uses big-nums. I don't think that's key to expressing the algorithm.
    It may be awkward to re-write numerical code to use an arbitrary
    precision arithmetic library, but the impact on the expression of the
    algorithm is not massive.
    Haskell is not know for its parsimony in respect of memory!

    Ben Bacarisse, Jun 3, 2014
  5. OK, psi is the sum of the reciprocals of the Fibonnaci numbers.

    So presumably there's a concise Haskell expression that will
    evaluate to psi by using the list. How many digits can you get?
    Malcolm McLean, Jun 3, 2014
  6. (usually phi)
    How many do you want? You need a high-precision float package to do any
    of this as Haskell only has rationals and plain old double-precision
    floats built-in, but there is a "computable real" package where you
    decide on the precision only when you come to print.

    The list of approximations can be done with the same trick of offset
    lists (zipWidth avoids the uncurry call):

    phi_approximations = zipWith ldiv (tail fib) fib
    where ldiv :: Integer -> Integer -> CReal
    ldiv a b = (fromInteger a)/(fromInteger b)

    To get sensible printing, you want to print about twice the number of
    digits as there are digits in the Fibonacci numbers being divided, so
    you could have a helper function (!! is the list index operator):

    phi_show n = showCReal (2*ndigits) (phi_approximations !! n)
    where ndigits = length $ show $ fib !! n

    About 0.6 seconds for nearly 42,000 digits. That's from the 100,000th
    approximation, i.e. the ratio of Fibonacci numbers 100,000 and 100,001.
    I have no idea if that is fast or not -- I've not tried any other

    As for your actual question about there being a concise expression for
    this, I am not good at Haskell golf. I am sure there is a neater
    expression, but I won't try to find it.
    Ben Bacarisse, Jun 3, 2014
  7. Kohtro

    Kaz Kylheku Guest

    Off the top of my head, this is imitable in TXR Lisp as follows, with an
    explicit destructive manipulation to close the self-reference:

    (defun fib ()
    (let ((fib (list 1 1)))
    (rplacd (cdr fib) [mapcar* + fib (rest fib)])

    (prinl [(fib) 0..15]))

    The basic concept is the same: overlap the fib sequence with itself,
    shifted by one position, and map through + to lazily continue, using
    (1 1) to get it started.


    $ txr fib.txr
    (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597)

    And so with that, it's obvious it can can be translated to intrinsic C code
    roughly like this:

    val fib(void)
    val fib = cons(one, cons(one, nil));
    rplacd(cdr(fib), lazy_mapcarv(func_n2(plus),
    cons(fib, cons(rest(fib), nil))));
    return fib;

    I'm not going bother testing this because I just know it works.

    Do you know the song, "Write in C"? Sing it with me!
    Kaz Kylheku, Jun 3, 2014
  8. Kohtro

    David Brown Guest

    It should also be perfectly possible to use a list of integer digits for
    decimals and for unlimited range integers, rather than standard floating
    point numbers. Make your integers as finite lists, and your ratio as an
    infinite list, using lazy evaluation. It's a /long/ time since I did
    this sort of thing, but at university I wrote a program in a functional
    programming language (not Haskell, but quite similar) to calculate the
    digits of pi in this way (from the Taylor series for atan(1/4)). The
    only limit on the output was due to memory on the computer, and the
    patience of the operator - the algorithm was not particularly efficient,
    but the program was elegant.
    David Brown, Jun 3, 2014
  9. phi is the ratio of the N+1/Nth Fibonnaci number, as N approaches
    infinity. But it also has a simple closed form expression.

    psi is the sum of the reciprocals, i.e.
    1/1 + 1/1 + 1/2 + 1/3 + 1/5 + 1/8 ...

    You need to calculate psi by summing, there is no closed form
    Malcolm McLean, Jun 3, 2014
  10. Kohtro

    BartC Guest

    Unless you need an exact value, this series seems to converge very quickly
    (to about 3.359886). You don't really need to sum all the terms.
    BartC, Jun 3, 2014
  11. Sure. I know that too. The question is the algorithm. Here you
    overwrite a cell to make a circular structure. Is that the same
    algorithm? I think it is debatable, but, to be honest, maybe it is not
    worth debating. We should maybe just agrees that some things are
    clearer and simpler to express in some languages. Questions of
    judgement and degree often generate more heat the light on Usenet.
    No, is it in the key of D? :)
    Ben Bacarisse, Jun 3, 2014
  12. I don't use standard floating point numbers. I am sure the CReal
    package does something like you suggest. I'm just avoiding duplicating
    that work.

    Ben Bacarisse, Jun 3, 2014
  13. Kohtro

    Kaz Kylheku Guest

    It's not exactly the same, but it's not very distant either.

    In the interpreted version where I use "let", I could make an operator which
    provides syntactic sugar for closing the self-reference which hides the
    destructive manipulation.

    The main concept is there: it's a small capsule of code which sets up a lazy
    structure corresponding to the Fibonacci series, produced by a function which
    maps + over its own results, shifted by one place.

    On the other hand, note that though I needed destructive assignment, I didn't
    need to "zip" the sequences together to form pairs, and then "uncurry" the +
    function to apply it to the pairs.
    The Haskell may be direct (something rare for Haskell), but it's obfuscated as

    This is way clearer and simpler to understand:

    (defun fib ()
    (let ((fib (list 1 1)))
    (rplacd (cdr fib) [mapcar* + fib (rest fib)])

    After you read this, you can exhale: "Ah, so that's the straightforward
    nuts and bolts of what the Haskell code is essentially doing".
    Kaz Kylheku, Jun 3, 2014
  14. Oh, I misread the question entirely, which is a shame because it is,
    perhaps, a little simpler (though slower to compute). One way (surely
    far less than optimal) is to write:

    phi_approximation :: [CReal]
    phi_approximation = scanl1 (+) (map (1/) (map fromInteger fib))

    and then just print this list. Alternatively, print an element and the
    next to see how many digits you've got right (yes, that's a rubbish
    method, but I don't want to spend much time on this). To get 1000
    digits takes about 0.6s.
    Ben Bacarisse, Jun 3, 2014
  15. That usually means better than linear. The convergence appears to be
    liner, but appearances can be deceiving.
    Ben Bacarisse, Jun 3, 2014
  16. I think I know what you mean -- an algorithm the just puts out decimal
    digits one by one (usually getting slower and slower!) for as long as
    you care to wait. If so, my last reply missed the point. Sorry.

    Yes, such a think is probably possible, (and they are very neat
    algorithms) but I went a different way round.
    Ben Bacarisse, Jun 3, 2014
  17. Yup, but if you consider zipping up two lists as part of the algorithm,
    then that's a part that's not been "expressed". (I think the uncurry
    (+) is of no significance -- in fact I should probably have used zipWith:

    fib = 1 : 1 : zipWith (+) fib (tail fib)


    I bet there will a few raised eyebrows at that remark!
    I find the Haskell very clear, but then I've been using it, and it's
    direct predecessors, for as long as I've been programming. Mind you,
    I've been using Lisp for about as long, so I am also very much at home
    with your version too. To me, they express slightly different things,
    but I may have set too fine a resolution on my algorithm detector.
    Ben Bacarisse, Jun 3, 2014
  18. Kohtro

    BartC Guest

    Possibly people wondering at the meaning of the square brackets.

    Maybe the first could be part of the identifier, but the second matching one
    by itself seems a bit of a coincidence.
    BartC, Jun 3, 2014
  19. Kohtro

    Kaz Kylheku Guest

    That part of the algorithm seems to reflect the coder's belief
    (right or wrong) that Haskell has no nice way to map over multiple lists.

    Zipping two lists into a list of corresponding pairs is just is
    (mapcar list list1 list2). If what we really want is to add
    corresponding list entries, we want (mapcar + list1 list2).
    Lisps usually have an N argument mapcar that will march through
    N lists in parallel and feed N arguments to the function.

    If all you have is "zip" and a map function that takes only unary
    functions and one list, then you need some hack workaround, like
    using a version of + that takes a list pair. You zip the lists up
    into pairs just so you can then map the pairs into this +.
    Aha, so there is your (mapcar + list1 list2); it is just called zipWith.

    I see that this doesn't take three lists! For that there is ...
    wait for it ... zipWith3.

    Camel case and numeric suffixes for number of arguments, *barf*.

    Why don't they just call this language Hassle?

    It makes things like "func_n1(plus)" in my C version look good!
    Kaz Kylheku, Jun 4, 2014
  20. Kohtro

    Kaz Kylheku Guest

    Those are the best use ever of square brackets in a Lisp dialect.

    Square brackets denote Lisp-1 style evaluation. Forms directly enclosed in
    square brackets which are symbols are evaluated in a folded function/variable
    namespace. This is beneficial for programming with higher-order functions,
    and with objects that behave like functions.

    Instead of (call var arg) or (mapcar (fun foo) list) you just write
    [var arg] or [mapcar foo list].

    Because sequences are functions (which map index positions to elements), square
    brackets provide indexing: [array 42]. Also, hash lookup: [hash foo].

    Basically, I have found a very clean, pragmatic way to combine Lisp-1 and
    Lisp-2, obtaining all the advantages of both.
    Kaz Kylheku, Jun 4, 2014
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.