Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue May 28, 2019 3:26 am

ScriptBasic,
I ran the Fibonacci Scheme code you posted running with Elk in TinyScheme and it produced the correct answer. What are your thoughts?
I'm not sure what you are asking exactly. But here goes:

Tiny Scheme is useless for the fibo challenge as it can't produce exact results bigger than fibo(70)

Even as an inexact result that is pretty poor as we should get to fibo(78) with 64 bit floats.

Using the complexity of the fast fibo algorithms for such small values of n makes no sense.

Elk Scheme is better, it gets us the correct fibo(4784969) in three and a half minutes on my PC.

I don't get the point of having an extension module for ScriptBasic to run Scheme (or any similar program), why not just use a generic "system" function to run a Scheme engine passing it the string to run?

Actually using Scheme from inside ScriptBasic like that must be hard, how do you develop/debug it?

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue May 28, 2019 4:04 am

Heater wrote:
Sat May 25, 2019 8:01 pm
Odd that, I have been rounding up Scheme engines. Got Racket and Chibi, today it was Chez Scheme and Guile.
I've been scheming with

Code: Select all

(define (fibo n)
    (cond ((= n 0) 0) ((= n 1) 1) (else
        (let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
            (if (even? n) (* a (+ (* 2 b) a))
                (let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
                    (if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(define (fiborun n)
    (if (= n 0) (exit) (fibo n)))

(define (fiboloop)
    (display "? ")
    (display (fiborun (read)))
    (display "\n")
    (fiboloop))

(fiboloop)
which is working fine under the fibench timing framework with Racket and Guile, except Racket gets the answer for fibo(61403) wrong.

Unfortunately, I can't find Chez or Chibi in the Raspbian repository. Did you compile these from source?

User avatar
John_Spikowski
Posts: 1334
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 4:40 am

Heater wrote: I don't get the point of having an extension module for ScriptBasic to run Scheme (or any similar program), why not just use a generic "system" function to run a Scheme engine passing it the string to run?

Actually using Scheme from inside ScriptBasic like that must be hard, how do you develop/debug it?
The TinyScheme extension allows me to load Scheme functions and call them from ScriptBasic. It also allows me to learn Scheme without the all or nothing approach. It's really easy to add C functions to TinyScheme. Checkout the MySQL extension for TinyScheme. It's designed to be embedded. (like ScriptBasic)

TinyScheme is the scripting engine in GIMP.

I'm curious. How often do you need to exceed the hardware's precision limitation and emulate large integers?
Last edited by John_Spikowski on Tue May 28, 2019 5:35 am, edited 8 times in total.

User avatar
John_Spikowski
Posts: 1334
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 4:51 am

@ejolson,

Your code works fine in TinyScheme.

Code: Select all

IMPORT ts.inc

sc = TS_New()
TS_Cmd sc, "(load \"init.scm\")"
ts_src = """
(define (fibo n)
    (cond ((= n 0) 0) ((= n 1) 1) (else
        (let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
            (if (even? n) (* a (+ (* 2 b) a))
                (let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
                    (if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(display (fibo 78))
(newline)

"""
PRINT FORMAT("%.0f",TS_Cmd(sc, ts_src)),"\n"
TS_Close sc


[email protected]:~/sb/examples/test$ time scriba fibo_eots.sb
8944394323791464

real	0m0.017s
user	0m0.013s
sys	0m0.004s
[email protected]:~/sb/examples/test$

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue May 28, 2019 6:25 am

ejolson,

That racket fibo above works fine with my Racket on my PC:

Code: Select all

$ racket -v
Welcome to Racket v6.7.
$ racket fibo.racket.scm | head -c 32
13139815501987632955443253884681
   ... Snipped meessage about broken pipe here.
$ racket fibo.racket.scm | tail  -c 32
5447320687563816790578645433977
$
I did a diff off the full output against the Python fibo. No problem.

All the language systems I used come from apt-get or are built from source.

The odd ball was GNU Smalltalk which gave incorrect results from apt-get but correct from my source build.

What is it about some programmers, they have the desperate urge to stuff everything into as few lines as possible thus obfuscating the codes operation and confusing the socks of the likes of me? :)

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue May 28, 2019 6:55 am

Heater wrote:
Tue May 28, 2019 6:25 am
ejolson,

That racket fibo above works fine with my Racket on my PC:

Code: Select all

$ racket -v
Welcome to Racket v6.7.
$ racket fibo.racket.scm | head -c 32
13139815501987632955443253884681
   ... Snipped meessage about broken pipe here.
$ racket fibo.racket.scm | tail  -c 32
5447320687563816790578645433977
$
I did a diff off the full output against the Python fibo. No problem.

All the language systems I used come from apt-get or are built from source.

The odd ball was GNU Smalltalk which gave incorrect results from apt-get but correct from my source build.

What is it about some programmers, they have the desperate urge to stuff everything into as few lines as possible thus obfuscating the codes operation and confusing the socks of the likes of me? :)
Sorry for confusing your socks, I reformatted the Scheme code so the parenthesis looked more appetising, at least to me. Brutally making it more compact also provided room on my screen for the interactive input and output routines needed for fibench.

The error I found could be a problem with the ARM version of Racket in Raspbian. The million-digit Fibonacci is fine, but not the one I mentioned. I'll rerun the test on an x86 machine to see what happens.

Update: Indeed Racket works fine on x86 but unfortunately not on Raspberry Pi with Raspbian. Do you know if the 64-bit ARM Racket executable works?

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue May 28, 2019 10:14 am

Racket Scheme calculates fibo (61403) perfectly on my Pi 3 running 64 bit Debian.

Code: Select all

$ uname -a
Linux pi64-aalto 4.11.12-pi64+ #1 SMP PREEMPT Sun Jul 30 20:18:20 CEST 2017 aarch64 GNU/Linux
[email protected]:~$ ^C

[email protected]:~$ time racket fibo.racket.scm | head -c 32 ; time racket fibo.racket.scm | tail -c 32
13139815501987632955443253884681
real    0m1.846s
user    0m1.660s
sys     0m0.189s
65447320687563816790578645433977
real    0m1.824s
user    0m1.625s
sys     0m0.202s
[email protected]:~$ 
fibo(4784969) is pretty speedy on the Pi 3:

Code: Select all

[email protected]:~$ time racket fibo.scm | head -c 32 ; time racket fibo.scm | tail -c 32
10727395641800477229364813596225
error writing to stream port
  system error: Broken pipe; errno=32

real    0m16.169s
user    0m15.920s
sys     0m0.249s
74856539211500699706378405156269
real    0m16.257s
user    0m16.011s
sys     0m0.233s
[email protected]:~$ 

User avatar
John_Spikowski
Posts: 1334
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 3:33 pm

There wasn't much interest in Elk on the AllBasic.info forum so I'm going to complete the TinyScheme API interface to allow C function use.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue May 28, 2019 4:13 pm

Heater wrote:
Tue May 28, 2019 10:14 am
Racket Scheme calculates fibo (61403) perfectly on my Pi 3 running 64 bit Debian.

Code: Select all

$ uname -a
Linux pi64-aalto 4.11.12-pi64+ #1 SMP PREEMPT Sun Jul 30 20:18:20 CEST 2017 aarch64 GNU/Linux
[email protected]:~$ ^C

[email protected]:~$ time racket fibo.racket.scm | head -c 32 ; time racket fibo.racket.scm | tail -c 32
13139815501987632955443253884681
real    0m1.846s
user    0m1.660s
sys     0m0.189s
65447320687563816790578645433977
real    0m1.824s
user    0m1.625s
sys     0m0.202s
[email protected]:~$ 
fibo(4784969) is pretty speedy on the Pi 3:

Code: Select all

[email protected]:~$ time racket fibo.scm | head -c 32 ; time racket fibo.scm | tail -c 32
10727395641800477229364813596225
error writing to stream port
  system error: Broken pipe; errno=32

real    0m16.169s
user    0m15.920s
sys     0m0.249s
74856539211500699706378405156269
real    0m16.257s
user    0m16.011s
sys     0m0.233s
[email protected]:~$ 
I'm currently a little disappointed with how Racket works on that $5 computer that came with a magazine subscription. Running the code

Code: Select all

#!/usr/bin/racket
#lang racket

(define (fibo n)
    (cond ((= n 0) 0) ((= n 1) 1) (else
        (let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
            (if (even? n) (* a (+ (* 2 b) a))
                (let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
                    (if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(display (fibo 61403))
results in the following

Code: Select all

$ time ./f61403.sh >f61403.out

real    0m6.010s
user    0m4.290s
sys 0m0.900s
$ head -c32 f61403.out ; echo
13139815501987631394568978726685
$ head -c32 classic.out ; echo
13139815501987632955443253884681
While most of the 6 seconds is run-time startup and excusable, the wrong answer less so. With wild scheme interpreters, just like wild horses, once adopted a person is forever responsible for their well being. Do you think a different kind of hay would help?

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue May 28, 2019 4:22 pm

I don't know about hay but we have now found two failures in interpreters and big integers on Raspbian: Racket Scheme and GNU Smalltalk, it's time to file some bug reports.

But where to file them? Raspbian maintainers, the Debian maintainers, upstream?

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue May 28, 2019 5:01 pm

Heater wrote:
Tue May 28, 2019 4:22 pm
I don't know about hay but we have now found two failures in interpreters and big integers on Raspbian: Racket Scheme and GNU Smalltalk, it's time to file some bug reports.

But where to file them? Raspbian maintainers, the Debian maintainers, upstream?
Horses always prefer upstream--I'm not so sure about interpreters. Here is another data point: Racket runs fine on 32-bit Intel architecture.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue May 28, 2019 5:15 pm

ejolson,
Horses always prefer upstream...
So do I.

However in the case of GNU SmallTalk I found that building from latest upstream sources resulted in a working big integer fibo. Clearly upstream would not be interested in hearing about a problem they don't have. That means somebody down stream needs to be told to stop shipping a buggy build of GNU Smalltalk. Is that the Raspbian folks or the Debian folks?

Perhaps the same applies to Racket.
Racket runs fine on 32-bit Intel architecture.
Ah, that was going to be my next question.

You sure you have the same Racket version on that 32 bit machine?

Curiouser and curiouser.

User avatar
John_Spikowski
Posts: 1334
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 5:28 pm

What Fibonacci has done for me.

* Stress test ScriptBasic's dynamic array stucture.

* Renew my interest in an expanded Scheme integration with ScriptBasic.

* An education in BIGINT and the languages that support it. The GMP library is a great resource if the need arises.

* I have wasted a lot of time on this topic / challenge.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue May 28, 2019 6:11 pm

ScriptBasic,

Fibonacci just keeps giving...

It has stressed at least two language implementations, supplied with Raspbian, to breaking point.

As for wast of time... it's half a year now and I'm still tinkering with the damn thing. With the off hand mention of a challenge I made a rod for my back.

I'm still wondering about this Scheme integration with BASIC idea ... I'm familiar with integrating languages into applications so as to provide the user with a means of customizing/configuring things. Been there, done that. But integrating a language into another language seems like a different thing to me.

It's a neat trick but:

What I have seen so far is not what I would call "integration". Can Scheme use variables and functions from ScriptBasic? Or vice versa?

As a means of learning Scheme it seems clunky. A Scheme string as a comment in BASIC means there is no user interaction with Scheme, like the usual REPL command line they provide. Editors cannot syntax highlight the Scheme or show how brackets match up or not. And so on.

How do Scheme error messages come out? If they do how does one match them up with the lines of Scheme comment in the BASIC?

Addressing all these things seems like a lot of work to me. Who would use it?

Sorry to sound so negative about it. Perhaps I just don't get the idea that you have.

User avatar
John_Spikowski
Posts: 1334
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 7:07 pm

What I have done with the TinyScheme integration is just minimal to get it running (3 functions) Take a look at the TinyScheme full API then you will understand the integration of the two languages. Both being embedded solutions makes this task rather easy compared to other languages.

The main theme here is dynamic runtime scripting with a seamless integration.

The V7 Javascript extension module would have been a good example of SB integration with a secondary language but it only runs on 64 bit Linux and the library is deprecated.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue May 28, 2019 7:35 pm

You might want to look at JerryScript http://jerryscript.net/ for an embedded Javascript implementation.

How would you handle the event loop of Javascript?

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Tue May 28, 2019 11:16 pm

Heater wrote:
Tue May 28, 2019 6:25 am
All the language systems I used come from apt-get or are built from source.
After I broke my Racket, I downloaded Chibi Scheme from the site

https://github.com/ashinn/chibi-scheme

typed "make" and then as root "make install" with the result

Code: Select all

echo "Generating images"
Generating images
cd / && LD_LIBRARY_PATH="/usr/local/lib:" DYLD_LIBRARY_PATH="/usr/local/lib:" CHIBI_MODULE_PATH="/usr/local/share/chibi:/usr/local/lib/chibi" /usr/local/bin/chibi-scheme -d /usr/local/share/chibi/chibi.img
Segmentation fault
Makefile:413: recipe for target 'install' failed
make: *** [install] Error 139
This was on a Raspberry Pi B+ running the latest version of Raspbian. It appears Chibi Scheme has escaped the roundup for now.

As a replacement Elk Scheme is currently computing Fibonacci numbers with neither the speed of a wild horse nor an antelope.

Similarly Chez scheme has just finished downloading. Running configure yields

Code: Select all

$ ./configure 
no suitable machine type found
try rerunning as ./configure -m=<machine type>
available machine types: a6le, a6nt, a6osx, i3le, i3nt, i3osx, ta6le, ta6nt, ta6osx, ti3le, ti3nt, and ti3osx
I found a link online describing how to cross-compile Chez scheme for ARM Android assuming you already have it installed on an Intel architecture machine.

Update: After computing a few numbers successfully Elk Scheme just output

Code: Select all

Panic: Visit: object not in prev space at 0xb6bc84d0 ('pair') 705 707 (dumping core).
The core dump appears to be dependent on the order of the Fibonacci numbers computed. The sequence in n which led to the crash was

Code: Select all

7499
3023
32
65089
17
15368
321
82985
3
600
10
76
2018
1186
1
195
2149831
0
Note it crashes while trying to compute fibo(2149831); however, if fibo(2149831) is computed first there is no crash. In keeping with the present theme, there is no crash when running on x86 regardless of whether fibo(2149831) is computed first or last.

Out of five Schemes Chibi and Chez failed to compile on the Raspberry Pi, Elk crashed, Racket gave wrong answers and Guile ran fine. That's not much of a roundup so far.
Last edited by ejolson on Wed May 29, 2019 1:09 am, edited 9 times in total.

User avatar
John_Spikowski
Posts: 1334
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue May 28, 2019 11:30 pm

Have you tried to install TinyScheme and run it from the console? No BIGINT support so you might not be interested.

You would think someone would have created a BIGINT library for Scheme written in Scheme.i might take a peek how Elk implemented it.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Wed May 29, 2019 12:47 am

From what I've read Tiny Scheme is missing essential features. For example here one finds the remark that
kishi wrote:Chibi is about the same size, and unlike TinyScheme is a real Scheme with hygienic macros and a fast VM (TinyScheme is hopelessly slow). It also has features like Huffman compressed immediate symbols to further reduce runtime heap usage - the raw image size isn't the whole story.
Now, getting back to the bugs,
ejolson wrote:
Tue May 28, 2019 11:16 pm
Out of five Schemes Chibi and Chez failed to compile on the Raspberry Pi, Elk crashed, Racket gave wrong answers and Guile ran fine. That's not much of a roundup so far.
For the record Racket also gives wrong answers on a Pi 3B and Elk still crashes in exactly the same way as on the Zero. The version of Racket is 6.7-3 armhf and the version of Elk is 3.99.8-4.1 armhf.

The results of all this scheming has reminded me of this thread.

User avatar
John_Spikowski
Posts: 1334
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Wed May 29, 2019 2:01 am

That seems depressing. Linux 32 bit is a dying environment no one wants to invest in anymore.

You may want to add the following to you gcc command line for ARM.

-fsigned-char

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Wed May 29, 2019 5:34 am

ScriptBasic,
Have you tried to install TinyScheme and run it from the console? No BIGINT support so you might not be interested.
TinyScheme is said to be "hopelessly slow" see above. Chibi is said to be much faster which may well be true but Chibi is already one of the slowest Schemes available. See Scheme benchmarks here: https://ecraven.github.io/r7rs-benchmarks/
You would think someone would have created a BIGINT library for Scheme written in Scheme.i might take a peek how Elk implemented it.
It crossed my mind to attempt creating Karatsuba in Tiny Scheme so as to get it to complete the Fibo challenge. That would at least be a good exercise in learning Scheme. However it would be so mind bendingly slow that I'm put off the idea.

I guess that nobody has created a BIGINT library in Scheme because most Schemes already handle big integers just fine. As a high level language should.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Wed May 29, 2019 5:46 am

Chibi Scheme builds and runs fine on my Pi 3 with 64 bit Debian:

Code: Select all

[email protected]:~/fibo_4784969/scheme$ time chibi-scheme fibo.chibi.scm | head -c 32
10727395641800477229364813596225
real    33m57.496s
user    33m56.368s
sys     0m0.925s
Interestingly that is only half the speed of running on my 64 Intel PC:

Code: Select all

$ time chibi-scheme fibo.chibi.scm | head -c 32
10727395641800477229364813596225
real    16m9.022s
user    16m0.141s
sys     0m0.234s
Usually I expect to see a PC/Pi performance ratio of about 10.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Wed May 29, 2019 6:59 am

Heater wrote:
Wed May 29, 2019 5:46 am
Chibi Scheme builds and runs fine on my Pi 3 with 64 bit Debian
That's good to know. I'll try on my Pi 3 under Raspbian next. Elk Scheme on 64-bit ARM also crashes here. Details are

Code: Select all

$ cat input.txt | ./elk.sh >output.txt

Panic: Visit: object not in prev space at 0x7fb0fea4d0 ('pair') 705 707 (dumping core).
./elk.sh: line 2: 21987 Aborted                 elk -l elk.sc
$ cat elk.sh
#!/bin/bash
elk -l elk.sc
$ cat elk.sc 
(define (fibo n)
    (cond ((= n 0) 0) ((= n 1) 1) (else
        (let* ((k (quotient n 2)) (a (fibo k)) (b (fibo (- k 1))))
            (if (even? n) (* a (+ (* 2 b) a))
                (let ((c (* (+ (* 2 a) b) (- (* 2 a) b))))
                    (if (= (modulo n 4) 1) (+ c 2) (- c 2))))))))

(define (fiborun n)
    (if (= n 0) (exit) (fibo n)))

(define (fiboloop)
    (display "? ")
    (display (fiborun (read)))
    (display "\n")
    (fiboloop))

(fiboloop)
$ cat input.txt 
7499
3023
32
65089
17
15368
321
82985
3
600
10
76
2018
1186
1
195
2149831
0
$ uname -a
Linux matrix 4.4.49-s5p6818 #1 SMP PREEMPT Fri Mar 23 15:29:14 HKT 2018 aarch64 aarch64 aarch64 GNU/Linux
Unsurprisingly, the same does not crash on either 32-bit or 64-bit Intel architectures. If you have the time I'd greatly appreciate it if you tried Elk on your ARM64 Debian distribution to see if you can reproduce the crash.

ejolson
Posts: 3422
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Wed May 29, 2019 7:44 am

ejolson wrote:
Wed May 29, 2019 6:59 am
Heater wrote:
Wed May 29, 2019 5:46 am
Chibi Scheme builds and runs fine on my Pi 3 with 64 bit Debian
That's good to know. I'll try on my Pi 3 under Raspbian next.
Trying to build Chibi on the Pi 3 under Raspbian ran into the same install-time crash as with the Zero. Then I built on 64-bit ARM and everything went fine. Finally, I copied over the three .img files from /usr/local/share/chibi on the 64-bit system to the Raspbian system and everything seems to work. Woohoo! Now there are enough Schemes.

Heater
Posts: 13111
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Wed May 29, 2019 7:49 am

I get the same error with your code and input data as shown above. Using Elk installed from apt-get on Pi 64 Debian:

Code: Select all

[email protected]:~/fibo_4784969/scheme$ elk -l  fibo.elk.sc
? 195
25299086886458645685589389182743678652930
...
... typed all the test numbers manually...
...
? 2149831

Panic: Visit: object not in prev space at 0x7f91b384d0 ('pair') 705 707 (dumping core).
Aborted
[email protected]:~/fibo_4784969/scheme$ elk -l  fibo.elk.sc
? 2149831
...
...7847308053219469
? 0
[email protected]:~/fibo_4784969/scheme$ 

Return to “General programming discussion”