gkreidl
Posts: 6120
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 7:53 am

jahboater wrote:
Fri Jul 05, 2019 7:18 am
gkreidl wrote:
Fri Jul 05, 2019 6:56 am
Having more "1"s in the lowest bits is important.

Code: Select all

pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py -t -n 4194320
Fibonacci(4194320) calculation took 0.2915217876434326 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py -t -n 4194319
Fibonacci(4194319) calculation took 0.3306257724761963 seconds
4194320 = 0x400010
4194319 = 0x40000f
Interesting.
But it may be implementation specific.
It doesn't make any difference to the execution time of mpz_fib_ui() for the two numbers above.
It does:

Code: Select all

pi@raspberrypi4:~/fibochallenge $ ./fibo_fdi.py -t -n -c 4194320
Fibonacci(4194320) calculation took 0.2462315559387207 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_fdi.py -t -n -c 4194319
Fibonacci(4194319) calculation took 0.21805834770202637 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_fdi.py -t -n -c 4194048
Fibonacci(4194048) calculation took 0.2125377655029297 seconds
The Parameter "-c = cheat" means, that my Python program calls the Fibo-Function built into GMP. You'll get a similar difference.
4194048 = 0x3fff00
has lots of 1s in the higher bits.
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer

jahboater
Posts: 4786
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 8:03 am

OK yes, my printout was not helpful. Its better printing the times in FP. Times from "clock_gettime( CLOCK_MONOTONIC"

Fibo(4194320) calculation time is 0.0333699 seconds
Fibo(4194319) calculation time is 0.0286553 seconds
Fibo(4194048) calculation time is 0.0254923 seconds

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 12:39 am

Are we at the fibo core yet? Can someone please come up with a new challenge?

How about GUI on the RPi challenge? Let's see what Python and others have to offer.

I'm doing a Simple Editor tutorial with ScriptBasic and IUP. Maybe that could be the basis for the challenge? (Build a simple editor)

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 6:07 am

ScriptBasic,
Are we at the fibo core yet?
Hah, not sure, every time I think we are done with this damn fibo challenge thing a new interesting fibo related thing comes up.
Can someone please come up with a new challenge?
Shouldn't you complete the first challenge properly before moving on to the next one? Not compulsory but would be satisfying.

Did you miss DavidS' 32 bit vs 64 bit ARM coding challenge yesterday? That was fun:
https://www.raspberrypi.org/forums/view ... 5#p1493385
How about GUI on the RPi challenge? Let's see what Python and others have to offer.

I'm doing a Simple Editor tutorial with ScriptBasic and IUP. Maybe that could be the basis for the challenge? (Build a simple editor)
OK, why not?

Feel free to start a new thread for your new challenge. You are going to need to define the requirements of the GUI fully and carefully. We had no end of feedback over the rules of the fibo challenge remember.

You could start off with a GUI for the big Fibonacci calculator, that's nice and simple :)

Here is mine: https://otaniemi.conveqs.fi:3000/public/fibo.html

Can you make it look so nice in ScriptBasic?
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 2:21 pm

I think the next challenge should result in something useful.

This fibo challenge is like claiming you stayed at a Holiday Inn. Where geniuses come from.

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 3:12 pm

ScriptBasic,
This fibo challenge is like claiming you stayed at a Holiday Inn. Where geniuses come from.
I have no idea what you mean by that. It sounds like the fibo challenge is being dismissed as trivial and/or useless. One should not be so quick to do that until one has produced a working solution oneself. I for one learned a lot during the course of the fibo challenge, most of it not about Fibonacci numbers.

The idea of a GUI challenge is interesting. But I have no idea what the challenge would entail.

Simply throwing up a bunch of buttons and text boxes and the like is kind of boring to do. Who would want to do it as an example software challenge?

Jazzing things up we end up getting into the ultimate GUIs, games...and the sky is the limit in size and complexity of code.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 3:26 pm

The challenge is to create a desktop simple editor. This is NOT a web browser challenge. IUP is one of many GUI toolkits to choose from.

I wanted to get the ScriptBasic submission completed as an example before creating the challenge thread.
Heater wrote: I have no idea what you mean by that.
I guess you would have to be from the US to get it.

Stayed at a Holiday Inn last night

User avatar
Paeryn
Posts: 2710
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 3:42 pm

ScriptBasic wrote:
Sat Jul 06, 2019 3:26 pm
The challenge is to create a desktop simple editor. This is NOT a web browser challenge. IUP is one of many GUI toolkits to choose from.
An editor of what? I think you need more specifications than just simple otherwise would this qualify (not tested, written on my phone whilst on a bus)

Code: Select all

#!/usr/bin/env python3
import tkinter as Tk

root = Tk.Tk()
entry_box= Tk.Entry(root)
entry_box.pack()
entry_box.insert(0, 'Edit me!')
root.mainloop()
It is a very simple editor.
She who travels light — forgot something.

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 3:47 pm

Let's put this on hold until the new challenge thread is started. This is still the fibo thread.

To get you thinking about what is coming.
  • Edit control must support rich text format using multiple fonts
  • A menu and toolbar will be required
  • A status bar will show line / column position
  • Open, SaveAs and Font select will be standard predefined dialogs you must interface with

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 4:29 pm

I was a t a meeting in the penthouse suite of a Holiday Inn in Helsinki the other week. It was just great. Sauna, huge jacuzzi the works.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Sat Jul 06, 2019 4:36 pm

There you go. How you were able to resolve your memory leak issue. 8-)

All we need to do with that clip is change the ending to say, "no but I bought a Raspberry Pi". :D

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

Project Digital Apocalypse Not Now

Mon Jul 08, 2019 8:46 pm

I, your humble programmer, who shares with you the distress, bugs and the debugging we have with computers, found myself sitting in front of a system called the Pi because I coded a big-number multiplication and produced the one-million digit Fibonacci number. I was caught up in the Karatsuba shuffle and heard behind me a voice as loud as an active cooling solution, which said, "Write a new program and run it on seven Raspberry Pi computers: the B, the B+, the 2B, the 3B, the Zero, the 3B+ and the 4B."

After weeks of traveling I was too tired to visit the Pi store and buy a 4B, so instead returned to the liberal frontier just in time for the explosion. While I pondered the new Windows text-editor challenge and new windows in general, I looked to the sky and noted the phase of the moon had indeed changed. Upon consulting the seven titles, I saw that "Project Digital Apocalypse Not Now" was next and everything suddenly made sense.

When user-programmable personal computers went out of fashion at the end of the golden age, they were replaced by office computers that ran shrink-wrapped software, then tablets, smart phones and chrome books which only ran digitally-signed software purchased directly from a vendor-specific online marketplace.

In the same way Luke Skywalker was Last Hope for the Galaxy, so too the Raspberry Pi. The second age of personal computing, for which this thread was initially named, was conceived in 2006 with a prototype based on the ATmega644 microcontroller and became reality in 2011 with the release of the original Pi B based on the BCM2835. As in the science fiction franchise, the future of the Rebel Alliance appeared doomed until the appearance of the Pi 4B led to a sudden victory in the Clone Wars.

But was this victory similarly hollow? Could the involved development cycle have allowed deep-learning neural networks to influence things behind the scenes as happened with the Dark Side and the Old Republic? Did any of the new hardware have hidden support for the half-precision 16-bit floating-point formats which powered those dangerous artificial intelligences? If so, the spinning bits of the digital apocalypse may already be upon us without anyone having noticed.

I carefully checked the Cortex-A72. That troublesome half-precision floating-point format was not there. However, in the midst of those processors cores I saw one like a GPU, wearing an ankle length wafer with a silicon sash around his interconnect. His transistors were white as hydrogen corrosion, the microcode like the sound of flushing water and in his QPUs were held a multitude of half-precision floating-point units.

After the second age of personal computing, not only were computers not user programmable, but neither were they human programmable. A sure sign of the digital apocalypse is when all software is created by emotional but powerful artificial intelligences. In a way different than how the Jedi confused the clones for the real enemy, the dangers of widely available half-precision hardware suitable for constructing neural networks was overlooked by the hobbyist and maker communities.

Before moving on, if that is even possible, I wanted to post the scripts used for generating the graphs which depict the results of the Fibonacci roundups that appear in this thread.

Recall fibench functions by means of rudimentary remote-procedure calls to a separately running Fibonacci calculator program. This provides a uniform way to measure the speed at which different codes run without contaminating the results with load-link time, startup or JIT compiler warmup. In this way three output files with names such as classic-1.out, classic-2.out and classic-3.out were created for each Fibonacci code. After doing this for five different Fibonacci codes the resulting fifteen files were preprocessed by a simple shell script and then graphed using gnuplot.

One of the representative shell scripts looked like

Code: Select all

#!/bin/bash
data='"classic-?.out" "visual-?.out" "integervol-?.out" "serial-?.out" "gmp-?.out"'
color='0x00CF0000 0x009F009F 0x00008F00 0x000000FF 0x00505050'
let n=1
for i in $data
do
    rgb=`echo $color | cut -d " " -f $n`
    echo $n
    f=`eval echo $i`
    for j in $f
    do
        echo $rgb
        cat $j | while read s
        do
            echo $s $rgb
        done
    done
    let n=n+1
done | shuf >zerotime.dat
Note that the above script creates the file zerotime.dat that contains a concatenation of the fifteen output files with a third column added to indicate color. As the data points will be graphed as a scatter plot, the last thing the script does is shuffle the order of the lines.

The gnuplot script looks like

Code: Select all

set terminal pngcairo enhanced color font "Courier-Bold" ps 2 size 1.8*5in,1.8*3.5in background rgb "0xFFFFFFFF"
set output 'zerotime.png'
set key left
set title "Measured Time Complexity of Fibonacci Codes"
set ylabel "seconds"
set xlabel "n"
set logscale x
set logscale y
set style data points
plot [1:] [0.0001:1000] \
"empty.dat" pt 7 ps 1 lc rgb "0x00CF0000" title "classic",\
"" pt 7 ps 1 lc rgb "0x009F009F" title "visual",\
"" pt 7 ps 1 lc rgb "0x00008F00" title "integervol",\
"" pt 7 ps 1 lc rgb "0x000000FF" title "serial",\
"" pt 7 ps 1 lc rgb "0x00505050" title "gmp",\
"zerotime.dat" using 1:2:3 pt 7 ps 0.2 lc rgb variable ti "",\
"zerotime.dat" using 1:2:($3+0xF0000000) pt 7 ps 0.2 lc rgb variable ti ""
Note that the data for the scatter plot is graphed twice, the second time with transparency for a slightly more artistic effect. This works for version 5.2 of gnuplot. Older versions may not have the same pngcairo output driver or transparency channels.
Last edited by ejolson on Mon Jul 08, 2019 9:29 pm, edited 1 time in total.

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

Re: Project Digital Apocalypse Not Now

Mon Jul 08, 2019 9:28 pm

It's not just me. This Fibonacci adventure has totally unhinged your mind as well.
Memory in C++ is a leaky abstraction .

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

Re: Project Digital Apocalypse Not Now

Tue Jul 09, 2019 5:48 pm

Heater wrote:
Mon Jul 08, 2019 9:28 pm
It's not just me. This Fibonacci adventure has totally unhinged your mind as well.
I agree that the apocalyptic genre sounds unhinged. So much so that it is easy to miss the meaning in it. The focus centers largely on human free will and dignity. Do computers control people or do people control computers?

The Fibonacci challenge has been fun. So much so that it is easy to miss the purpose behind it. Can the second age of personal computing be prolonged by creating a society in which knowing how to read and write computer programs is as common as traditional types of literacy? While it seems simple minded that coding big-number multiplication while telling jokes could make any difference, it is amazing how much difference little things like the Raspberry Pi itself have made towards creating a computer-literate society.

The golden age ended when people started believing anything they wanted to do with their personal computers could be better done with shrink-wrapped software no programming necessary. Even corporations tried this approach, yet the legacy of treasured Cobol outlasted repeated attempts to do away with in-house software. Similarly, Basic is widely discussed on the Raspberry Pi forum as well as Python, which was more recently engineered according to similar principles.

Today the value of being able tell a computer what to do by writing a program is widely accepted. There are details, such as what constitutes a good first programming language and to what degree those languages satisfy the principles set forth by Kurtz and Kemeny. However, since computer literacy is now thought to be so fundamental, it has become part of the national curriculum alongside traditional reading, writing and arithmetic. What could go wrong?

The digital apocalypse is an advanced stage of digital feudalism in which all programs and the means to make them involve deep-learning convolutional neural networks controlled by emotional but powerful artificial intelligences. Although the second age of personal computing has again given people a taste of the liberation that comes from being able to code any new algorithm they are able to think up that the computer is capable of performing, it's human nature to trade freedom for convenience.

Could it ever be convenient to use a computer without knowing how to automate even the simplest task? Except for computing million-digit Fibonacci numbers, is it possible all human-written software could be replaced by artificial intelligence, half-precision floating point and appropriately trained deep-learning neural networks?

What can be done to avoid the digital apocalypse?

User avatar
davidcoton
Posts: 4206
Joined: Mon Sep 01, 2014 2:37 pm
Location: Cambridge, UK

Re: Project Digital Apocalypse Not Now

Tue Jul 09, 2019 10:27 pm

ejolson wrote:
Tue Jul 09, 2019 5:48 pm
What can be done to avoid the digital apocalypse?
There are two options.
  1. Use computers, learn to get the best out of them by, dare I mention the P word, programming.
  2. Ignore computers.
There are two outcomes. I think there is a 1 to 1 correspondance between the options above and these outcomes, but further research is needed.
  1. The computers will end up controlling the users
  2. The computers will end up controlling the non-users.
tl;dr Conclusion
Nothing.
Signature retired

User avatar
jojopi
Posts: 3085
Joined: Tue Oct 11, 2011 8:38 pm

Re: A Final Fidonacci Challenge

Thu Jul 11, 2019 6:17 pm

I have not followed all of the past discussion on this problem, so apologies if this idea has been proposed before.

Without mentioning names, I recently became aware of a solution in BBC BASIC V on RISC OS. It does not give a fully correct result do to a slight bug in the carry handling. But what really stuck me was that it may be 53500 times faster than it should be.

It has also been very hot here; though certainly not 320 kelvins; I may be delirious; I think this idea originally came to me in a fever dream. It is only about 37 times faster than my first attempt, but it does have the advantage of not requiring gmpy2, so I think it is finally a legal solution for this thread.

Without further adon't, I present fido.py on a Pi2B:

Code: Select all

pi@pi2b:~ $ time python3 fido.py 4784969 |head -c32; time python3 fido.py 4784969 |tail -c32
10727395641800477229364813596225
real    0m1.312s
user    0m1.177s
sys     0m0.092s
4856539211500699706378405156269

real    0m1.229s
user    0m1.174s
sys     0m0.067s
And the code:

Code: Select all

import sys, math
n = int(sys.argv[1]) if len(sys.argv) > 1 else 4784969

from decimal import *
getcontext().prec = 2560
sqrt5 = Decimal(5).sqrt()
prep = ((sqrt5 + 1) / 2) ** n / sqrt5
limbs, getcontext().prec = 10**getcontext().prec, 1+int(Decimal.logb(prep))

cache = {x:x for x in range(2)}
def fido(n):
  if n in cache: return cache[n]
  k = (n + 1) // 2
  fj, fk = fido(k-1), fido(k)
  if n & 1: cache[n] = pow(fj,2,limbs) + pow(fk,2,limbs)
  else: cache[n] = (2*fj + fk) * fk % limbs
  return cache[n]

try: print((prep+fido(n)).quantize(Decimal(1)))
except IOError as e: pass # BrokenPipeError
I really hoped that this technique would allow for the calculation of much larger fidonacci numbers, but I found that Python's decimal module is not a true arbitrary-precision implementation. Actually it is intended for producing textbook-compatible results, and a million digits seems to be close to its limit.

Another, more obvious, drawback is that this kind of optimization does not convert well to trancendental problems such as the approximation of pi. I have to consider that a defect of this particular challenge, really.

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

Fibonacci Challenge

Thu Jul 11, 2019 6:40 pm

AIR wrote: IF you properly exit an sb app, the memory is released.

With most apps, if you send a sigkill to it while monitoring for leaks, you will see that some of the memory allocated is not properly released.

So, the 'problem' is that sb never gets the chance to release allocated memory because of an artificial non-real world test.

I've tested this with a loop of 100 iterations while monitoring with valgrind.  I didn't see the memory usage jump up to the extent that others have.  And memory was released at the end.

That's as far as I'm going with this.  If y'all feel that the module is problematic, then either provide a fix or don't use it.
I agree with AIR and I'm not chasing any leak ghosts.

We achieved the million digit Fibonacci challenge and our efforts deserve to be included in the repo.
Last edited by John_Spikowski on Thu Jul 11, 2019 6:42 pm, edited 2 times in total.

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 6:41 pm

jojopi,

Interesting and interesting...

I don't know anything about any RISC OS solutions. No working version has been demonstrated as far as I know. If it is producing a wrong result then it is a "no show". If it is producing a wrong result then it may well be thousands of times faster. I mean, a random number generator could do that :)

I was not aware of that floating point thing you are doing in Python. Did it produce a correct million digit result? It's not clear to me what the advantage of using big floats would be, is it really faster than big integer maths in Python?
I have to consider that a defect of this particular challenge, really.
I don't understand what you mean by "defect" of the Fibonacci Challenge. What was wrong with it?
Memory in C++ is a leaky abstraction .

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 7:36 pm

davidcoton wrote:
Tue Jul 09, 2019 10:27 pm
There are two outcomes. I think there is a 1 to 1 correspondance between the options above and these outcomes, but further research is needed.
  1. The computers will end up controlling the users
  2. The computers will end up controlling the non-users.
That sounds pretty grim, but I think I have come up with a solution: Using the new Pi 4B to compute the smallest billion-digit Fibonacci number should be sufficient to keep those deep-learning convolutional neural networks occupied for a bit longer and give us humans more time to improve our own programming techniques and as a result avoid the impending digital apocalypse.

Unfortunately, due to spending all my money on airline travel and not being given one for free, I don't have a 4B at the moment. Also, it is not clear the current 32-bit LPAE kernel would be up to computing that billion-digit number in the first place. However, in preparation for both of the above events to transpire, I have modified method1.c to compute the 4784971964th Fibonacci number, which happens to be the smallest one that has a billion digits.

The code is

Code: Select all

/*  billion.c -- Compute the 4784971964th Fibonacci Number
    Modified July 11, 2019 by Eric Olson from method1.c

    This program uses the doubling formulas

        F(2k) = F(k)[2F(k+1)-F(k)]
      F(2k+1) = F(k+1)[2F(k+1)-F(k)]+(-1)^(k+1)

    and

      F(2k+1) = F(k)[2F(k)+F(k+1)]+(-1)^(k)
      F(2k+2) = F(k+1)[2F(k)+F(k+1)]

    The results of this code can also serve as a point of comparison
    to implementations of the doubling formulas using other languages
    that leverage GMP big numbers behind the scenes.  */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

static mpz_t a,b,t1;
void fibowork(long int n){
    if(n==0){
        mpz_set_ui(a,0);
        mpz_set_ui(b,1);
        return;
    }
    fibowork(n/2);
    if(n%2==0){
        // [a,b]=[a*(2*b-a),b*(2*b-a)-(-1)^k]
        mpz_add(t1,b,b); mpz_sub(t1,t1,a);
        mpz_mul(a,a,t1); mpz_mul(b,b,t1);
        if(n%4==0) mpz_sub_ui(b,b,1);
        else mpz_add_ui(b,b,1);
    } else {
        // [a,b]=[a*(2*a+b)+(-1)^k,b*(2*a+b)]
        mpz_add(t1,a,a); mpz_add(t1,t1,b);
        mpz_mul(b,b,t1); mpz_mul(a,a,t1);
        if(n%4==1) mpz_add_ui(a,a,1);
        else mpz_sub_ui(a,a,1);
    }
    return;
}

void fibo(long int n){
    if(n<2){
        mpz_set_ui(b,n);
        return;
    }
    fibowork((n-1)/2);
    if(n%2==0){
        // b=b*(2*a+b)
        mpz_add(t1,a,a); mpz_add(t1,t1,b); mpz_mul(b,b,t1);
    } else {
        // b=b*(2*b-a)-(-1)^k
        mpz_add(t1,b,b); mpz_sub(t1,t1,a); mpz_mul(b,b,t1);
        if(n%4==1) mpz_sub_ui(b,b,1);
        else mpz_add_ui(b,b,1);
    }
    return;
}

int main(){
    mpz_init(a); mpz_init(b); mpz_init(t1);
        fibo(4784971964l);
        mpz_out_str(stdout,10,b);
        printf("\n");
    mpz_clear(t1); mpz_clear(b); mpz_clear(a);
    return 0;
}
and the output when run on a Ryzen 7 Pro 1700 desktop computer is

Code: Select all

$ time ./billion >f4784971964.out

real    7m17.697s
user    7m11.150s
sys 0m6.172s
$ head -c32 f4784971964.out ; echo
11726845151952222692730258923866
$ tail -c32 f4784971964.out 
6906960656263025463452143611773
$ md5sum f4784971964.out 
3a4b122de35c728b0c212edc4ca95884  f4784971964.out
$ time sed "s/2/\n/g" <billion.out >edited.out

real    0m16.038s
user    0m14.824s
sys 0m1.204s
$ md5sum edited.out
9e8d0e7b9b79081872025a8e07fcce7f  edited.out
$ head edited.out
117
684515195



69
730
589
3866748077
83984377
$ tail edited.out
057040768934640
437
799
156713
7831380479
933531115903861
3906133146093458416906960656
630
546345
143611773
Note that the code billion.c uses GMP but not the built-in mpz_fib_ui function, because the number n=4784971964 is already too big to fit in an unsigned integer. Although this is not fully compliant with the million-digit Fibonacci challenge, since GMP is needed to even build the GNU compiler collection it will likely be available by default on any system that has gcc.

While running, the resident size of the processes remained under 3.5GB; however, virtual memory usage topped 4.3GB. Therefore, it appears the Pi 4B equipped with 4GB RAM would need a fully functional 64-bit kernel to compute the billion-digit Fibonacci number.
Last edited by ejolson on Thu Jul 11, 2019 8:22 pm, edited 1 time in total.

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:20 pm

ScriptBasic,
I agree with AIR and I'm not chasing any leak ghosts.
As I have told you before, this is not a ghost. It's a bug. It's an ever increasing use of memory until the thing crashes (or get's killed by the OS Out Of Memory reaper). During which time it starves other processes on the machine of memory and generally messes things up. See my new results below below.

I agree with Air's analysis but perhaps not with his conclusions:

1) This may well be an "artificial non-real world test" but if memory is being squandered here then it will be squandered wherever else this is used. Most of the "real-world" software I have ever written is expected to run forever, without needlessly consuming resources and crashing. That would be regarded as a serious bug.

2) I am not surprised that valgrind does not detect any memory leak. I have tried it myself already. Here is what a very strongly suspect is happening:

You told me that ScriptBasic does not use malloc and has it's own memory manager/allocator. It seems very likely that that customer allocator is holding on to live pointers to memory that ceases to be used, whilst endlessly grabbing new memory as things run.

In this situation Valgrind will not see a problem, all the memory is referenced by a pointer somewhere (in the custom allocator). It's just that this memory is never used again as the allocator goes on to new space.

Then of course, if one terminates the program, the allocator no doubt releases all the memory it has, so Valgrind never sees a problem.

Air is right, the module is problematic, I'm not about to start studying ScriptBasic to fix it, and I will not be using it.

Let me know when it get's fixed and included in the standard ScriptBasic release and I will add your solution to the fibo challenge repo. As promised.

Now to my results. I have just run this code again:

Code: Select all

import gmp2.bas

function fibo(n)
    a = 1
    b = 0
    p = 0
    q = 1

    while n > 0
        if (n % 2) = 0 then
            psq   = gmp2::mul(p, p)
            qsq   = gmp2::mul(q, q)
            twopq = gmp2::mul(p, q)
            twopq = gmp2::mul_si(twopq, 2)
            p     = gmp2::add(psq, qsq)
            q     = gmp2::add(twopq, qsq)
            n = n / 2
        else
            bq    = gmp2::mul(b, q)
            aq    = gmp2::mul(a, q)
            ap    = gmp2::mul(a, p)
            bp    = gmp2::mul(b, p)
            a     = gmp2::add(bq, aq)
            a     = gmp2::add(a, ap)
            b     = gmp2::add(bp, aq)
            fibo  = b
            n = n - 1
        end if
    wend
end function

count = 0
while 1
    f = fibo(4784969)
    count = count + 1
    print f,"\n"
    print "Count: ", count,"\n"
wend
That is your 1milfibo with a simple endless loop to run the fibo forever. Do let me know if you see anything wrong with this.

This is what happens:

Code: Select all

Tasks:   9 total,   2 running,   7 sleeping,   0 stopped,   0 zombie
%Cpu(s): 11.0 us,  3.4 sy,  0.0 ni, 85.4 id,  0.0 wa,  0.1 hi,  0.0 si,  0.0 st
MiB Mem :   8169.4 total,   3471.9 free,   4473.6 used,    224.0 buff/cache
MiB Swap:  17177.4 total,  17150.1 free,     27.3 used.   3565.3 avail Mem

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
  631 heater    20   0 1675124   1.6g   1300 R  89.9  19.9   3:11.79 scriba
    1 root      20   0    8312    144    116 S   0.0   0.0   0:00.10 init
    3 root      20   0    8312    100     64 S   0.0   0.0   0:00.00 init
    4 heater   20   0   18304   5656   5540 S   0.0   0.1   0:01.45 bash
  310 root      20   0    8312    100     64 S   0.0   0.0   0:00.00 init
  311 heater   20   0   18304   5604   5496 S   0.0   0.1   0:00.10 bash
  599 heater   20   0   17360   2208   1496 R   0.0   0.0   0:00.54 top
  622 root      20   0   15612   2072   2048 S   0.0   0.0   0:00.04 su
  623 heater    20   0   12240   2336   2232 S   0.0   0.0   0:00.26 bash

Code: Select all

....
753075056218657196441932393464334826295933658166608470284692225373725373897596352132746754917096933249041342716132648351306358960276912379779548359662123974673178961370380669138017064573175529579344050069967214425788878450757018865691080604649238041660668972297841899441410955952199093230662515228401051114812321029531207832876870087454540927898489890806067034196931622252893057035920930130552038239931974615715617623206204585291487968755147324883784916338945806361951766313865956891695455563801462249978567353436540666740580717167763216988216644330074030719891463180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269
Count: 75

Code: Select all

Tasks:   9 total,   2 running,   7 sleeping,   0 stopped,   0 zombie
%Cpu(s): 11.2 us,  2.1 sy,  0.0 ni, 86.6 id,  0.0 wa,  0.1 hi,  0.0 si,  0.0 st
MiB Mem :   8169.4 total,   1129.8 free,   6815.6 used,    224.0 buff/cache
MiB Swap:  17177.4 total,  17150.1 free,     27.3 used.   1223.2 avail Mem

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
  631 heater    20   0 4210008   4.0g   1300 R  89.7  50.2   8:08.85 scriba
    1 root      20   0    8312    144    116 S   0.0   0.0   0:00.10 init
    3 root      20   0    8312    100     64 S   0.0   0.0   0:00.00 init
    4 heater   20   0   18304   5656   5540 S   0.0   0.1   0:01.45 bash
  310 root      20   0    8312    100     64 S   0.0   0.0   0:00.00 init
  311 heater   20   0   18304   5604   5504 S   0.0   0.1   0:00.10 bash
  622 root      20   0   15612   2072   2048 S   0.0   0.0   0:00.04 su
  623 heater    20   0   12240   2336   2232 S   0.0   0.0   0:00.26 bash
  632 heater   20   0   17216   2164   1496 R   0.0   0.0   0:00.09 top

Code: Select all

....
7167763216988216644330074030719891463180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269
Count: 174
Sorry I did not catch the memory usage prior to the crash, it was up to 70 something perecent.

Code: Select all

...
6204585291487968755147324883784916338945806361951766313865956891695455563801462249978567353436540666740580717167763216988216644330074030719891463180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269
Count: 803
Segmentation fault (core dumped)
Do try this yourself if you are not convinced.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 4786
Joined: Wed Feb 04, 2015 6:38 pm

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:23 pm

ejolson wrote:
Thu Jul 11, 2019 7:36 pm
Note that the code billion.c uses GMP but not the built-in mpz_fib_ui function, because the number n=4784971964 is already too big to fit in an unsigned integer.
It is on the 32-bit Pi. Its an unsigned long, so on my Intel PC, mpz_fib_ui() takes ...

fibo( 10000000000 ) takes 91.3227 seconds

the 10 billionth term, which seems impressive to me.

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:34 pm

jahboater wrote:
Thu Jul 11, 2019 8:23 pm
ejolson wrote:
Thu Jul 11, 2019 7:36 pm
Note that the code billion.c uses GMP but not the built-in mpz_fib_ui function, because the number n=4784971964 is already too big to fit in an unsigned integer.
It is on the 32-bit Pi. Its an unsigned long, so on my Intel PC, mpz_fib_ui() takes ...

fibo( 10000000000 ) takes 91.3227 seconds

the 10 billionth term, which seems impressive to me.
That's a good point.

How long does it take to compute the 4784971964th Fibonacci number?

Do you get the same answer I found with my code?

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:36 pm

Sorry!

I'm not wasting another minute of my time on fibo.

Fill the moat and draw the bridge, see if I give a ...

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:46 pm

No one is asking you to waste your time on fibo. If it's not fun for you there is no reason to do it.

However one would expect bugs in the big integer extension to be fixed if it is to be included in a ScriptBasic release.

That is a pretty nasty attitude given that I have just wasted an hour of my life again testing the thing for you.
Memory in C++ is a leaky abstraction .

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

Re: Project Digital Apocalypse Not Now

Thu Jul 11, 2019 8:48 pm

ejolson,

4784971964, what a sweet and enticing number.

So eerily similar to the now famous 4784969.

My C++ bint class is calling to me, it can handle a paltry 4784971964 as a parameter for n.

I must resist...I must resist...
Memory in C++ is a leaky abstraction .

Return to “General programming discussion”