You are not logged in or registered. Please login or register to use the full functionality of this board...
SIGN IN Join Our Community For FREE


Small coding challenge (computer needed)
06-11-2017, 10:48 PM
Post: #1
 (Print Post)
Small coding challenge (computer needed)
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?
Find all posts by this user
Like Post
06-11-2017, 11:17 PM
Post: #2
 (Print Post)
RE: Small coding challenge (computer needed)
Code Snippet: [Select]
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 File(s) Image(s)
   

B += _
Find all posts by this user
Like Post
06-11-2017, 11:56 PM (This post was last modified: 06-11-2017 11:58 PM by STxAxTIC.)
Post: #3
 (Print Post)
RE: Small coding challenge (computer needed)
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 Snippet: [Select]
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 Snippet: [Select]
largediv(
    1.(for(<i,1,2495,1>,{0})),
    999999999999999999999998999999999999999999999999
  )
Find all posts by this user
Like Post
The following 3 users Like STxAxTIC's post:
bplus, figosdev, Waltersmind (Admin)
06-12-2017, 12:32 AM
Post: #4
 (Print Post)
RE: Small coding challenge (computer needed)
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 += _
Find all posts by this user
Like Post
06-12-2017, 09:53 AM (This post was last modified: 06-12-2017 09:55 AM by STxAxTIC.)
Post: #5
 (Print Post)
RE: Small coding challenge (computer needed)
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 Snippet: [Select]
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.
Find all posts by this user
Like Post
The following 1 user Likes STxAxTIC's post:
bplus
06-12-2017, 11:08 AM
Post: #6
 (Print Post)
RE: Small coding challenge (computer needed)
Oh, so the for loop just creates the decimal part of 1.00000... (2495 0's)

Thanks

B += _
Find all posts by this user
Like Post



Forum Jump:


User(s) browsing this thread: 1 Guest(s)




QB64 Member Project - Connect Four
QB64 Member Project - Pivet version one
QB64 Member Project - STxAxTIC 3D World
QB64 Member Project - Color Rotating Text
QB64 Member Project - Qubic
QB64 Member Project - Line Thickness
QB64 Member Project - Inside Moves
QB64 Member Project - Touche
QB64 Member Project - Martin Fractals version three
QB64 Member Project - Martin Fractals version two
QB64 Member Project - Input
QB64 Member Project - Kings Court
QB64 Member Project - Amazon
QB64 Member Project - Kings Valley verion one
QB64 Member Project - Kings Vallery version two
QB64 Member Project - Rubix's Magic
QB64 Member Project - Quarto
QB64 Member Project - Score 4
QB64 Member Project - Domain
QB64 Member Project - Bowditch curve
QB64 Member Project - Foursight
QB64 Member Project - Color Triangles
QB64 Member Project - Splatter
QB64 Member Project - Kobolts Monopoly
QB64 Member Project - OpenGL Triangles
QB64 Member Project - Rotating Background
QB64 Member Project - Algeria Weather
QB64 Member Project - Martin Fractals version four
QB64 Member Project - Isolation
QB64 Member Project - MAPTRIANGLE
QB64 Member Project - Spinning Color Wheel
QB64 Member Project - Dreamy Clock
QB64 Member Project - Spiro Roses
QB64 Member Project - Dakapo
QB64 Member Project - Othello
QB64 Member Project - Blokus
QB64 Member Project - Pivot version two
QB64 Member Project - Point Blank
QB64 Member Project - Basic Dithering
QB64 Member Project - ARB Checkers
QB64 Member Project - RGB Color Wheel
QB64 Member Project - Red Scrolling LED Sign
QB64 Member Project - Swirl
QB64 Member Project - Sabotage
QB64 Member Project - Exit
QB64 Member Project - Martin Fractals version one
QB64 Member Project - Overboard
QB64 Member Project - 9 Board
QB64 Member Project - Full Color LED Sign