A fun problem re-occured to me that I figure would be fun to share. And that is:

Write a program to produce (many of) the Fibonacci sequence (1 1 2 3 5 8 ...) in the fewest number of lines. Is a recursive function always shorter than a procedural one? Is there a method that beats them both?

06-12-2017, 01:56 PM This post was last modified: 06-12-2017, 01:58 PM by STxAxTIC. Edited 0 times

Thanks for responding bplus. Your submission resembles (or is exactly) the irreducible mousetrap that solves this problem. Even a recursive method does it in just about the same number of lines, perhaps fewer, but with way more computational overhead.

I want to show a trick though that solves this problem. You will need a largenum math library to do the following calculation:

Code:

1

divided by

999999999999999999999998999999999999999999999999

That's not just a line of 9's. Notice the 8 in the middle. Doing that problem, you get a very long string with lots of zero like this:

And voila, the fibonacci numbers, the first few dozen at least, appear neatly as the nonzero digits in the result.

In sxript, to produce this (and to limit the number of digits to 2 thousand something) I write:

06-12-2017, 11:53 PM This post was last modified: 06-12-2017, 11:55 PM by STxAxTIC. Edited 0 times

Heya bplus.

Guilty, I tend to always have a trick up my sleeve, even if the challenge seems un-baited. Anyway, you ask a good question.

In the spirit of trying to be a "functional" language with no side effects, Sxript has no hidden states, especially global ones, unless you really really mean it. Combine this with the fact that I used an arbitrary-precision math routine to do the division, and there is suddenly an infinite pitfall to dodge: Long division wouldn't know when to stop. Ask a computer to calculate 1/3=0.33333333333 ... and the number is governed by its type. This doesn't pan out well when your number size is basically unlimited.

One solution, for division at least, is to tune the result's precision based on the precision of the numerator, as in:

and so on (it's really more optimized than what I just said but the spirit is the same).

Okay, now onto the actual syntax.

The "1." in the code returns exactly that - a one and then a decimal. The for loop right next to it is designed to stick a bunch of zeros after "1." The structure there is:

Code:

for(<variable,low,high,step>, {
body
})

In place of {body}, we just have {0} for this example. The limit of 2945 was chosen kindof carefully - you'll notice that if you play with the windows size (actually you can't because its a picture) - the columns of Fibonacci numbers wouldn't stack up. It just so happens that

[1.(2495 zeros)] divided by [all that long number with the 9's] = just enough digits to fit squarely in the window chosen.

DIM x(-1 TO 1000)
x(-1) = 1
FOR y = 1 TO 50
x(y) = x(y - 2) + x(y - 1)
PRINT x(y),
NEXT

6 lines... The smallest line count yet, if we count colons as line breaks the same as we do CHR$(10) line endings. I just think the proper line endings just makes it a little more readable for us, and it really doesn't save any room on the disk to use : instead...