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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 12:38 pm

Perhaps. That was a little cheeky challenge in itself.

And I have confessed my sin. See above.

And I have not included it in the challenge repo.

And I did ask the judgement of others about it.

It's still an edge case and an open question as far as I'm concerned. Because:

a) It does not use any non standard libraries. Which is a requirement.

b) The code is all mine, despite being Javascript generated from my C++. Does using code generators disqualify entries?

c) My C++ was actually derived from my Javascript Karatsuba in the first place!

d) Provided I ever figure out how to get Emcripten to generate Javascript that works, rather than WASM of course. (Which will no doubt be 10 or more times slower)

I think ejolson has a good suggestion. Create a "disqualified" category in the challenge repo for entries that are interesting but don't make the grade by virtue of using external libraries or being transpiled from other languages or whatever. Then even ScriptBasic making a call to GMP's fibo function could make an appearance. Or the Deban GNU Smalltalk version that produces an incorrect result!

What does everyone (anyone) think?
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 1:42 pm

Heater wrote:
Mon Jun 10, 2019 12:38 pm
What does everyone (anyone) think?
Sounds OK.
Your pure Javascript entry (hand written by you) is of course totally valid.
The C++ version, machine translated to Javascript, should go in the disqualified section IMHO.

I guess my one line C/GMP entry has to go in the disqualified section.

jalih
Posts: 94
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 2:22 pm

Heater wrote:
Mon Jun 10, 2019 12:38 pm
I think ejolson has a good suggestion. Create a "disqualified" category in the challenge repo for entries that are interesting but don't make the grade by virtue of using external libraries or being transpiled from other languages or whatever. Then even ScriptBasic making a call to GMP's fibo function could make an appearance. Or the Deban GNU Smalltalk version that produces an incorrect result!
Does that mean, you accept this 8th entry into "disqualified" category?

Code: Select all

\
\ Fibonacci with million digits
\

: bits?  \ n -- nbits-1
  n:ln 2 n:ln n:/ n:int ;


: fibo-loop
  >r                             \ Put loop counter on r-stack
  \ a b
  2dup 2 n:*                     \ a b a 2b
  over n:-                       \ a b a (2b-a)
  n:* -rot                       \ d=(2b-a)*a a b
  dup n:* swap dup n:* n:+       \ d=(2b-a)*a e=b*b+a*a
  r> r@ swap n:shr 1 n:band if
    dup  \ a b b
    rot  \ b b a
    n:+  \ b c=b+a
  then ;


: fibo  \  n -- fibo(n)
  >r    \ Put n on r-stack
  F0 F1 \ a b
  ' fibo-loop 0 r@ bits? loop-
  rdrop
  drop ;  \ a


: app:main
  d:msec >r
  4784969 fibo
  "%.f" strfmt \ Convert result to just an 'int' string.
  s:len . " digits:" . cr
  . cr
  d:msec r> n:-
  . " msec" . cr
  bye ;
  
It takes about 450 millisecs to calculate fibo(4784969) and output the full result into console on my PC. On my ROCK64 it's a little slower but still fast as hell!

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 3:03 pm

jalih,
Does that mean, you accept this 8th entry into "disqualified" category?
This restriction on 8th distribution dictates that no I will not:

"Unfortunately, yes. Due to Israeli export laws, residents of the following countries may not purchase 8th: Cuba, Iran, Lebanon, North Korea, Sudan, and Syria."

From the 8th FAQ: https://8th-dev.com/faq.html
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 4:33 pm

I just had an interesting conversation with the primary developer of FidoBasic. Fido is barking mad about the cat memes and all the attention that LOLCAT-inspired programming language has been getting. Specifically, "what good is high-performance parallel processing without n-level meta programming?" When asked whether an alpha or beta release would be available soon, the developer whined, "without meta-sophistry the original design may need revisions, because using fractions and irrational quantities for Basic line numbers is not working out so well."

I personally prefer the category name of extraordinary because it sounds better than disqualified. Also, the phrase "program X is qualified to be included in the extraordinary category" makes more sense to me than the alternative.

It is possible high-quality built-in big-number support is why the 8th interpreter is considered to be munitions-grade export restricted software. From this point of view it may be a blessing in disguise that all of our hand-coded Fibonacci programs fall short compared to the performance of GMP. Leaving out the operations of big-number division, remainder and multiplication modulo big divisors further ensure our efforts, except for avoiding a digital apocalypse, have no practical use outside the increasingly important field of large Fibonacci numbers.
Last edited by ejolson on Mon Jun 10, 2019 5:44 pm, edited 10 times in total.

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 5:15 pm

When I die, please note on my gravestone that I achived the holy grail of 1 million digits.

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 8:11 pm

Oddly enough wen I transpile the C++ Bint class to a pure Javascript Module (No WASM) it does actually produce a result when run the browser. Under node.js it runs without output.

Here it is running: http://otaniemi.conveqs.fi:3000/public/fibo.html

Execution time is up to 30 seconds on my PC. Which is twice as fast as the fibo.js that uses Javascript's BigInt type.

That is all down to the greatly reduced time to print the result using Bint. Actual calculation time with JS BigInt's is much less.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 8:13 pm

ScriptBasic,
When I die, please note on my gravestone that I achived the holy grail of 1 million digits.
If you post your latest big fibo code I will add it to the entries.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 8:32 pm

ejolson,
I personally prefer the category name of extraordinary because it sounds better than disqualified. Also, the phrase "program X is qualified to be included in the extraordinary category" makes more sense to me than the alternative.
Hmm...

I take "disqualified" as meaning "deemed not to qualify". See dictionary.

As such your phrase becomes: "program X is qualified to be included in the deemed not to qualify category"

Which is too weird.

What a can of worms. I was thinking of calling the category something like:

"Nice Try"

"No Biscuit"

"Attendance Award"

"Also ran"

Or some such. I see that whatever it's called it will offend whoever's solution ends up in it.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 8:46 pm

Heater wrote:
Mon Jun 10, 2019 8:32 pm
I was thinking of calling the category something like:

"Nice Try"

"No Biscuit"

"Attendance Award"

"Also ran"

Or some such.
Hm. If you want spaces in the directory names, how about

"Group A"

and

"Group B"

instead of ordinary and extraordinary?

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 9:08 pm

I suggest dropping the rules and happily accept any 1 mil fibo entry. Stop being so picky with other peoples time.

I feel my solution of GMP was as valid as anyone else's approach to meeting the challenge. I would draw the line at no shell based fibo calls.

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 9:13 pm

Good point. I hate spaces in directory/file names.

Thing is, I was never intending to make any judgement of the entries. Not in terms of expressiveness, performance, or whatever. If they did the job with in the specification, as vague as it is, they were included and could speak for themselves.

Then we got the ALGOL version which can't do a million digits. Included because of historical interest.

The C version using GMP's fibo. Included basically as a reference of correctness and ultimate performance.

This C++, derived from JS and transpiled back to JS thing. Because I think it's interesting.

Potentially ScriptBasic because ScriptBasic was feeling unfairly ignored.

I just want a single word that means "Failed to meet requirements but noteworthy anyway"
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 9:19 pm

Potentially ScriptBasic because ScriptBasic was feeling unfairly ignored.
I did the fibo using classic.bas and GMP. Why should ScriptBasic be ignored?

I think the fibo challenge would have more value if using BIGINT isn't allowed.

I would like to see a classic.bas done in Python. (no BIGINT)
Last edited by John_Spikowski on Mon Jun 10, 2019 9:48 pm, edited 1 time in total.

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 9:47 pm

ScriptBasic,
I suggest dropping the rules and happily accept any 1 mil fibo entry.... I feel my solution of GMP was as valid as anyone else's approach to meeting the challenge.
That really does not work for me:

All challenges have rules. There is no challenge without rules. The whole exercise becomes void without them.

The whole point of the challenge, the spirit of the thing, was to demonstrate:

a) The result can actually be achieved in the language of ones choice.

b) How easily the solution can be arrived at in the language and how nicely it expresses the solution.

c) Of lesser concern, within reason, performance.

Simply calling an existing fibo function written in a different language does not satisfy any of the above goals.

I think my big mistake here was choosing Fibonacci as the task. Had I just made up some other crazy calculation we would not be debating use this short cut.

I'd be happier if the ScriptBasic solution simply used GMP to do the big maths whilst showing how the fibo alogoritm would look in Script Basic. At least that would be something.
Stop being so picky with other peoples time.
What?

I have no say in how people use their time.
I think the fibo challenge would have more value if using BIGINT isn't allowed.
That does not work for me either.

The fact that some languages seamlessly support big number types is what makes them very clearly expressive of the solution to the fibo problem. Which is most of the point of the challenge.

If you want to create a Python version that restricts itself to 32 or 64 bit integers and implements it's own Karatuba multiply or whatever, like classic.bas or fibo_karatsuba.js or fibonacci.c, I look forward to seeing it.
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 9:51 pm

This is a biased challenge with Heater making the rules.

I'm out.

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 10:01 pm

Hey, it was my challenge. Of course a made the rules. With input from and consensus from other participants as it happens.

Calling that "biased" is uncalled for. It's no more biased than the rules of Soduku or chess or a million other problems.

Anyway, I was thinking...

If we install the latest ScriptBasic, and it included the fibo function in it's libraries/modules out of the box. Then there could be no objection to the one line ScriptBasic solution to the challenge.

Can we do that? If so how?
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 10:06 pm

Sure. As soon as @ejolson finishes the GMP extension module. It shouldn't take long, it's only 4 or 5 addition function calls to GMP. No need to worry about rethurn buffers, SB handles it for you.

Let's see if "it would be great if" still holds water.

I wouldn't mind if he calls his new BIGINT extended creation FiboBasic. 8-)
Last edited by John_Spikowski on Mon Jun 10, 2019 10:14 pm, edited 1 time in total.

hippy
Posts: 6284
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 10:08 pm

Heater wrote:
Mon Jun 10, 2019 3:03 pm
jalih,
Does that mean, you accept this 8th entry into "disqualified" category?
This restriction on 8th distribution dictates that no I will not:

"Unfortunately, yes. Due to Israeli export laws, residents of the following countries may not purchase 8th: Cuba, Iran, Lebanon, North Korea, Sudan, and Syria."

From the 8th FAQ: https://8th-dev.com/faq.html
So how exactly does this make the 8th entry unacceptable, what rule has it broken ?

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 10:36 pm

If the C one line Fibo author would extend the interface to BIGINT math using string buffers, I could have a ScriptBasic extension module of it in about an hour.

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 10:41 pm

hippy,
So how exactly does this make the 8th entry unacceptable, what rule has it broken?
Why the unwritten rule of course :)

OK then. I hereby declare that the solution to the problem of calculating the first Fibonacci number with one decimal million digits using the 8th language is a perfectly acceptable solution to the fibo(4784969) challenge and is in accordance to the criteria expressed by the challenge creators.

However, it's not going into any git repository of mine because:

1) I cannot in good conscience promote, encourage or support the use of non Open Source, commercial, software. Especially programming languages.

2) Regardless of 1) I see no reason to advertise/support commercial products without remuneration/benefit of some kind.

Now that's just me. I'm sure many will not be sympathetic with my stance on this.

The git hub repository is of course public and open for use freely, so feel free to fork it and make whatever additions one likes.
https://github.com/ZiCog/fibo_4784969
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 11:31 pm

ScriptBasic,
If the C one line Fibo author would extend the interface to BIGINT math using string buffers, I could have a ScriptBasic extension module of it in about an hour.
You mean like this:

Code: Select all

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

// Compute the n'th Fibonacci number and place result into string s
// Be sure s is big enough !
void fibo(int n, char* s) {
    mpz_t res;
    mpz_init(res);

    mpz_fib_ui(res, n);

    mpz_get_str (s, 10, res);
}

int main(int argc, char* argv[] ) {
    int n = 4784969;               // The first Fibonacci number with a million digits
    char resultString[1000001];    // A million digits plus null.

    if (argc >= 2) {
        n = atol(argv[1]);
    }

    if (n > 4784973) {
        printf("Result would be too big for available output buffer.\n");
        exit(-1);
    }

    fibo(n, resultString);

    printf("%s\n", resultString);

    return (0);
}
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Mon Jun 10, 2019 11:44 pm

Thanks. That is the direction I would like to go with ScriptBasic.

I would like to see the full set of math functions like addition, subtraction, multiply and divide with GMP BIGINT.

I understand there is a GMP library for Python and seems to be a lot faster than native BIGINT support. Maybe someone could do a comparison fibo in Python using GMP. I'm surprised Python doesn't have a fibo function like GMP.

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 12:12 am

ScriptBasic,

You mean like:

Code: Select all

    char resultString[1000001];
    mpz_t x;
    mpz_t y;
    mpz_t result;
    mpz_init(x);
    mpz_init(y);
    mpz_init(result);
    int BASE = 10;

    mpz_set_str (x, "98273948723984798237498723948729387492837498723984792387498723987492837", BASE);
    mpz_set_str (y, "43827508347509872304598720398475023874509832475087230489570238745098237450982374508723", BASE);

    mpz_mul (result, x, y);      // result = x * y

    mpz_get_str (resultString, 10, result);
    printf("%s\n", resultString);
Other operations go the same. It's all in the GMP manual:

https://gmplib.org/manual/Integer-Arith ... Arithmetic
Memory in C++ is a leaky abstraction .

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 12:18 am

ScriptBasic wrote:
Mon Jun 10, 2019 11:44 pm
I understand there is a GMP library for Python and seems to be a lot faster than native BIGINT support. Maybe someone could do a comparison fibo in Python using GMP. I'm surprised Python doesn't have a fibo function like GMP.
gmpy

https://pypi.org/project/gmpy2/

which includes MPC for arbitrary precision complex numbers

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

Re: A Final Fibonacci Challenge

Tue Jun 11, 2019 12:30 am

Maybe we are talking more than few new functions. Looks like a good model to work from.

Heater,

Can you post a set of GMP functions in C that would allow doing the fibo traditionally assuming BIGINT support?

Return to “General programming discussion”