Small coding challenge (computer needed)
#1
Hello all,

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?
Reply
#2
Code:
a=1:b=1:?a,b,:for i=1 to 45:c=a+b:?c,:a=b:b=c:next:?
at 45 I exceed the integer limit for SmallBASIC.


Attached Files Thumbnail(s)

B += x
Reply
#3
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:

[Image: fibsho.png]

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:

Code:
largediv(
    1.(for(<i,1,2495,1>,{0})),
    999999999999999999999998999999999999999999999999
  )
Reply
#4
I knew you had something up your sleeve! A pleasure being your straight man STxAxTIC. Wink

Could you explain your for line specially the {0}? and 2495 significance?
B += x
Reply
#5
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:

largediv(1,3) = 0.3
largediv(1.0,3) = 0.33
largediv(1.0000,3) = 0.33333

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.
Reply
#6
Oh, so the for loop just creates the decimal part of 1.00000... (2495 0's)

Thanks
B += x
Reply
#7
Code:
_DEFINE A-Z AS _UNSIGNED _INTEGER64
PRINT "1";
FOR l = 1 TO 50
    x = x + 1
    A = 1
    B = 1
    FOR F = 1 TO x - 1
        t = B
        B = A + B
        A = t
    NEXT
    PRINT B;
NEXT
END

Although it is not short, it could be concantenated into one line..
dndbbs project:

Links to my MUD: (strictly 16-bit); AKA XP:

Dndbbs executables
http://www.filegate.net/pdn/pdnbasic/dnd50a1e.zip

Dndbbs source
http://www.filegate.net/pdn/pdnbasic/dnd50a1s.zip

Dndbbs upgrade
http://www.filegate.net/pdn/pdnbasic/dnd50a1u.zip

DNDDOOR - https://bit.ly/EriksDNDDoor DUNGEON - https://bit.ly/EriksDungeon
Interpreter - https://bit.ly/EriksSICK Hex Editor - https://bit.ly/EriksHexEditor Utilities - https://bit.ly/EriksUtils
QB45 files: - https://bit.ly/EriksQB45 QB64shell - https://bit.ly/QB64shell Some old QB64 versions: - https://bit.ly/OldQB64
Reply
#8
b=1:?b,:WHILE c<9E6:c=a+b:?c,:a=b:b=c:WEND
I like to program in BASIC
With code that is simple and slick
I learnt it in school
And it is still cool
So it is my number one pick
Reply
#9
OK Adrian!  
 
Code:
? "Bplus:"
b=1:?b,:while b>0:c=a+b:?c,:a=b:b=c:wend
a=0:b=0:c=0
?:? "Adrian:"
b=1:?b,:WHILE c<9E6:c=a+b:?c,:a=b:b=c:WEND
pause

Big Grin 2 less, powered by the plus
B += x
Reply
#10
ok , you win!!... Smile
I like to program in BASIC
With code that is simple and slick
I learnt it in school
And it is still cool
So it is my number one pick
Reply
#11
Code:
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...
Reply
#12
Hi Steve, 
Code:
b=1
?b,
while b>0
  c=a+b
  ?c,
  a=b
  b=c
wend


Yep!  Thumbs Up

I offer a prize Chocolate Chip Cookie or Money Bag or Beer    Huh   

Oh Hot Coffee looks good!

Thanks Walter
B += x
Reply
#13
Code:
b=1
?b,
while b
  c=a+b
  ?c,
  a=b
  b=c
wend
 
thanks for the prize, bplus!
I like to program in BASIC
With code that is simple and slick
I learnt it in school
And it is still cool
So it is my number one pick
Reply
#14
Ah now that I've been shown the way, there is this in SmallBASIC:
Code:
dim x(-1 to  46)
x(-1) = 1
for y in seq(1, 46, 46) do x(y) = x(y-2) + x(y-1)
for y in seq(1, 46, 46) do ? x(y),
B += x
Reply
#15
Hey Adrian,
 
Not sure I like the ending but another 2 off! 
Why didn't I think of that?
B += x
Reply
#16
hi bplus,

actually you can knock out another 2 if we are going with this program listing on multiple lines, we don't need commas any more.

Code:
b=1
?b
while b
  c=a+b
  ?c
  a=b
  b=c
wend
I like to program in BASIC
With code that is simple and slick
I learnt it in school
And it is still cool
So it is my number one pick
Reply
#17
OK man! now you are topping yourself! Big Grin

At this rate, in a couple more days, I will be seeing the Fibonacci in my dreams and you won't have to type a letter!
B += x
Reply
#18
Thanks guys, now I have a brain worm stuck in my head. Here is another way to do 6 lines in either QB64 or SmallBASIC:
Code:
fib 1, 0, 32
SUB fib (a, b, l)
    c = a + b
    PRINT c,
    IF l > 0 THEN fib b, c, l - 1
END SUB
B += x
Reply