In the beginning was personal computing, and personal computing was with Basic, and personal computing was Basic. The same was in the beginning with Basic. All programs were made with Basic; and without Basic was not any thing made that was made. In Basic was programming; and that programming was the code of programmers. And the code shineth in the forum; and the forum comprehended it not.
As the phase of the moon has changed, so has the title of this thread. As the title of this thread has changed to the Final Fibonacci Challenge, here are some Pi Zero results showing the relative scaling of five famous Fibonacci codes:
- classic--the line numbered Basic program classic.bas which is compatible with the original version of MITS/Altair Basic compiled with Free Basic. This program uses floating-point arrays to store the big Fibonacci numbers.
- integervol--a variation of the classic line numbered Basic program integer.bas which instead uses 32-bit integer arrays again compiled with Free Basic. Note that the volatility keyword was added in the needed places to work around bugs in how gosub was implemented by the C code-generator backend.
- serial--based on the OpenMP code parallel.c but compiled for serial operation without the -fopenmp using gcc 6.3.0.
- gmp--a simple call to the mpz_fib_ui subroutine from the GMP multi-precision library.
- visual--the program visual.bas written in structured Basic with arrays of 32-bit integers compiled with vbnc 0.0.0.5943 and executed using mono 4.6.2.
To obtain timing metrics independent of run-time system startup each program was modified to repeatedly present a "? " prompt to input the number n after which the resulting value of the n-th Fibonacci number F(n) was output. Rather than take the timings by hand with a stop watch, it was then decided to create a separate benchmarking program that ran each of the corresponding Fibonacci codes under a pty device to automatically calculate the computational time needed to calculate Fibonacci numbers for randomly chosen values of n between 1 and 4784969. Graphs and output will be included in a separate post soon.
While the C code ran in a fairly straightforward way under the pty device, the Basic implementations had various difficulties. For example, when executing the statement
input n
Free Basic wrote the "? " prompt to standard input rather than standard output. Since the same pty device is used for both input and output, this wouldn't have been a problem except for another bug. When run under the pty device (or even ssh) the Free Basic input routines occasionally fail to process characters as they are typed. The result being that the calculation of F(n) doesn't begin reliably upon receiving the value of n.
It turns out that Free Basic reads input more reliably from a pipe. Therefore the following was used as a workaround
cat | ./classic
However, at this point the "? " prompt generated by the input statement disappears because it is being written to standard input. Therefore, the Basic code was changed to read
print "? ";:input "",n
so the prompt is output to standard output.
It should also be noted without the pipeline that Free Basic outputs escape codes to the pty device unless the TERM environment variable is unset. While there is some sense in this, I find no reason to add escape codes to the output of a console-mode text-only program.
Even when TERM was unset, Visual Basic refused to stop writing escape codes to the pty device. However, sending the output through a pipe did prevent the escape codes from appearing. Therefore, the work-around needed for running the Visual basic code under the benchmarking program was
mono ./visual.exe | cat
which then prevented the automatic generation of unwanted escape codes.
If this thread were titled Why avoid Basic, the need for workarounds to interactively drive standard input and output of a text-only program through a pty device could be seen as a reason for avoidance.
For reference the benchmarking program is
Code: Select all
/* fibench -- Benchmark a Fibonacci Program.
Written May 22, 2019 by Eric Olson
This program provides a benchmarking harness for interactive
programs that compute million-digit Fibonacci numbers using
the following protocol:
1. The program being timed presents a prompt "? " without
the quotes and waits for the number n.
2. Upon receiving the number n followed by a line-feed
the program then output the n-th Fibonacci number on
one line followed by a line feed.
3. The process repeats until n=0 is received upon which
the program exits.
*/
#include <stdio.h>
#include <math.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <pty.h>
#include <sys/time.h>
#include <time.h>
#include <signal.h>
#include <termios.h>
#include <gmp.h>
#define MAXFN 4784969
#define MAXDG 1048576
#define FSEED 2019
static int fibskip=MAXFN, fibiter=1000, fibrep=1, fibfail=1;
static char *fibprog="internal";
static int fibmaster,fibpid;
static char fibbuf[MAXDG],gmpbuf[MAXDG];
static char rdrbuf[4096];
static int rdrcur,rdrend;
static mpz_t fibres;
void onint(){
if(fibpid) kill(fibpid,SIGINT);
exit(1);
}
void onquit(){
if(fibpid) kill(fibpid,SIGQUIT);
exit(1);
}
void onkill(){
if(fibpid) kill(fibpid,SIGKILL);
exit(1);
}
#ifdef CLOCK_MONOTONIC_RAW
static struct timespec tic_start;
static void tic() {
clock_gettime(CLOCK_MONOTONIC_RAW,&tic_start);
}
static double toc() {
struct timespec tic_stop;
clock_gettime(CLOCK_MONOTONIC_RAW,&tic_stop);
double sec=tic_stop.tv_sec-tic_start.tv_sec;
return sec+(tic_stop.tv_nsec-tic_start.tv_nsec)*1.0e-9;
}
#else
static struct timeval tic_start;
static void tic() {
gettimeofday(&tic_start,0);
}
static double toc() {
struct timeval tic_stop;
gettimeofday(&tic_stop,0);
double sec=tic_stop.tv_sec-tic_start.tv_sec;
return sec+(tic_stop.tv_usec-tic_start.tv_usec)*1.0e-6;
}
#endif
static int fibgetc(){
while(rdrcur==rdrend){
rdrend=read(fibmaster,rdrbuf,sizeof(rdrbuf));
if(rdrend<0) onkill();
rdrcur=0;
}
int c=rdrbuf[rdrcur++];
// printf("c=%d %c\n",c,isprint(c)?c:'?');
return c;
}
static void fibqmsp(){
int fibhang=0;
for(;;){
int c=fibgetc();
if(!fibhang&&c=='?'){
c=fibgetc();
if(c==' ') return;
}
if (c=='\n'||c=='\r') fibhang=0;
else fibhang=1;
}
}
static void fibnum(){
int i=0;
for(;;){
int c=fibgetc();
if(isdigit(c)) fibbuf[i++]=c;
if(i&&(c=='\n'||c=='\r')) {
fibbuf[i]=0;
return;
}
}
}
int fiborun(){
if(strcmp(fibprog,"internal")){
unsetenv("TERM");
unsetenv("DISPLAY");
unsetenv("SSH_CLIENT");
unsetenv("SSH_CONNECTION");
unsetenv("SSH_TTY");
execlp(fibprog,fibprog,(char *)0);
}
for(;;){
printf("? ");
char buf[128];
fgets(buf,sizeof(buf),stdin);
int n=atoi(buf);
if(!n) return 0;
mpz_fib_ui(fibres,n);
gmp_printf("%Zd\n",fibres);
}
}
static int fibench(){
mpz_init(fibres);
struct termios termiost;
cfmakeraw(&termiost);
if(!(fibpid=forkpty(&fibmaster,0,&termiost,0))){
return fiborun();
}
signal(SIGINT, onint);
signal(SIGQUIT, onquit);
signal(SIGKILL, onkill);
FILE *fibinp=fdopen(fibmaster,"w");
for(int k=0;k<fibrep;k++){
int n=7499;
srandom(FSEED);
printf("#%8s %12s -- %s\n","n","Tn",fibprog);
fflush(stdout);
for(int i=-1;i<fibiter;i++){
if(n<=fibskip&&n>=1){
fibqmsp();
char fibn[128];
tic();
fprintf(fibinp,"%d\n",n); fflush(fibinp);
fibnum();
double t=toc();
mpz_fib_ui(fibres,n);
gmp_sprintf(gmpbuf,"%Zd",fibres);
int r=strcmp(fibbuf,gmpbuf);
if(fibfail&&r){
printf("#F(%d) failed!\n",n);
printf("#<%s>\n#<%s>\n",fibbuf,gmpbuf);
exit(1);
}
if(i>=0) printf("%c%8d %12.4e\n",r?'#':' ',n,t);
fflush(stdout);
}
n=MAXFN;
if(i>=0) n=n*exp(-log(MAXFN)*random()/RAND_MAX)+0.5;
}
if(k+1<fibrep) printf("\n\n");
}
fprintf(fibinp,"0\n"); fflush(fibinp);
return 0;
}
static void fibhelp(){
printf(
"fibench -- Benchmark a Fibonacci Program.\n"
"Usage: fibench [options] program\n"
"Options:\n"
"\t-i \tIgnore failures when GMP doesn't match.\n"
"\t-l n\tPerform n number of different timings.\n"
"\t-r n\tRepeat the entire benchmark run n times.\n"
"\t-s n\tSkip computing Fibonacci numbers greater than n.\n"
"\t-h \tPrint this help.\n"
);
exit(1);
}
int main(int argc, char *argv[]){
int opt;
while((opt=getopt(argc,argv,"il:r:s:"))!=-1){
switch(opt){
case 'i':
fibfail=0;
break;
case 'l':
fibiter=atoi(optarg);
break;
case 'r':
fibrep=atoi(optarg);
break;
case 's':
fibskip=atoi(optarg);
break;
default:
fibhelp();
}
}
if(optind<argc) fibprog=argv[optind];
return fibench();
}
Changes to the classic.bas and integer.bas programs were
Code: Select all
280 dim m(d9*m9)
290 m0=1:print "? ";:input "",n:if n=0 then stop
300 a=m0:m0=m0+1+d9:b=m0:m0=m0+1+d9
310 t1=m0:m0=m0+1+d9:t2=m0:m0=m0+1+d9
400 r0=n:gosub 1000
420 r7=b:gosub 7000
430 goto 290
Changes to the parallel.c program were
Code: Select all
for(;;){
printf("? ");
char buf[128];
fgets(buf,sizeof(buf),stdin);
n=atoi(buf);
if(n==0) return 0;
work(n);
}
Changes to the visual.bas program were
Code: Select all
while 1
dim s as string
console.write("? ")
s=console.readline()
n=val(s)
if n=0 then return 0
fibo(n)
bigprint(b)
end while
Update: The program fibench.c was updated with minor changes to allow more convenient timings for Fibonacci codes that don't always give the correct answer.
that old memory is still intact 
