Go to advanced search

by ejolson
Mon Dec 31, 2018 12:10 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

No normal human being is going to be using that stuff. I'm not sure many normal people could even sit through the video. While it's well known that If something is hard to do then it's not worth doing. I suspect what you did with object oriented operator overloading in C++ is significantly harder t...
by ejolson
Sun Dec 30, 2018 1:54 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

When my amusement with line-numbered BASIC wears off, I'll improve the C code with a better implementation of the doubling formulas if someone has not done so already. It should be a straight-forward conversion of the corresponding routines in the FreeBASIC code. To check whether the line-numbered ...
by ejolson
Sun Dec 30, 2018 11:00 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Heater wrote:
Sun Dec 30, 2018 10:54 am
BUT here is an odd thing. Whilst playing with this I got the feeling that using -O2 was faster.
Is it possible you have -march and -mtune set for the wrong processor?

Does the O(n^2) multiplication routine with delayed carry vectorize on 64-bit ARM? What about in 32-bit mode?
by ejolson
Sun Dec 30, 2018 1:21 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

It looks like this // This Fibonacci version derived from ejolson's doubling formula C example. bint a; bint b; static void fiboEjOlson(const int n) { if (n == 0) { a = zero; b = one; return; } fiboEjOlson(n / 2); bint ta = a; bint tb = b; if (isEven(n)) { b = (a * a) + (b * b); a = ta * ((tb + tb)...
by ejolson
Sat Dec 29, 2018 11:54 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Looking at the output of gprof I see that almost 80% of the time is spent in the O(n^2) multiplication. Which is a direct translation of ejolson's mul_bn() in C to C++. This 80 percent explains why the assembler optimized arithmetic kernels in GMP are so effective even though they constitute only a...
by ejolson
Sat Dec 29, 2018 11:39 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Heater wrote:
Sat Dec 29, 2018 6:24 pm
I found one big contributor to the C++ performance boost over the C version.
I tried to summarise the optimisations missing from the C version in this previous post.
by ejolson
Sat Dec 29, 2018 1:59 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

ejolson, There are actually two related but different parameters here: the cross over point and how much to delay the carry. Thanks for the clarification. I obviously don't understand that delayed carry as well as I thought, I'll have to study how those bits are jumping in more detail. Note that fu...
by ejolson
Sat Dec 29, 2018 1:47 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

It remains to be seen whether a careful use of integer data types will allow the line-numbered BASIC Fibonacci program to meet or outperform the others. With the creation of the interactive programming environment called BASIC by Kemény, Kurtz and a host of undergraduate students at Dartmouth Colle...
by ejolson
Sat Dec 29, 2018 2:58 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

This indicates that the speed of the line-numbered BASIC code when compiled with FreeBASIC is about 10 times slower than the C code. The likely reason for the speed difference is the fact that floating point is slower than integer arithmetic. Moreover, it appears to be single precision. To the prog...
by ejolson
Sat Dec 29, 2018 1:32 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

jahboater, ...are you sure its not overflowing here? Not sure of anything yet. Before I took the ejolson's mul_bn() into use I fuzz tested it with about half a million multiplies of numbers from 9 to 387 digits wide. Comparing the results with GMP. No problem. Built into my bint class I have two fa...
by ejolson
Fri Dec 28, 2018 10:46 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Of course if BASE could be a "power of two" things would fly (get rid of most of the divides?) The difficulty in using base 2 for the computation is the subsequent conversion to base 10 for printing. Coding an efficient base 2 to base 10 conversion routine piles yet another conquer and divide algor...
by ejolson
Fri Dec 28, 2018 4:35 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

For sake of discussion and to keep this off-topic thread on topic, I have written a program in classic line-numbered BASIC that uses Karatsuba multiplication and the doubling formulas to compute the 4784969th Fibonacci number. The program was developed in FreeBASIC using the -lang qb option; however...
by ejolson
Fri Dec 28, 2018 3:02 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Sounds reasonable. Integer DIV is notoriously the slowest operation we have on the processors around today. I can't get my head around how to do it exactly or when things overflow if I do! The current C and FreeBASIC codes demonstrate one way to delay the carry in the O(n^2) multiplication. Another...
by ejolson
Fri Dec 28, 2018 2:05 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

That means when adding big ints made of these one can do 4 or 16 additions into the same result array without worrying about carry propagation. Then do a final pass through the array propagating the carry. If 50 percent of execution time is spent doing software division and the number of divisions ...
by ejolson
Fri Dec 28, 2018 1:09 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

jahboater, This is odd ... Instruction counts ... 13 billion instructions vs 10 billion So why is the C++ one faster? What is the tool you are using to count those instructions? I have no idea. We are in the twilight zone of optimizing code for modern processors. It's all smoke and mirrors and you ...
by ejolson
Thu Dec 27, 2018 9:15 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

There is a problem with the 32-bit Pi version:- $ gcc -O3 -s fibo.c -o fibo_c $ g++ -O3 -s -DMUTABLE fibo.cpp -o fibo_cpp $ time ./fibo_cpp >/dev/null real 2m6.049s user 2m6.020s sys 0m0.020s $ time ./fibo_c >/dev/null real 0m16.949s user 0m16.917s sys 0m0.030s When division is done in software, th...
by ejolson
Thu Dec 27, 2018 4:04 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

With the rest of the code now better tested and seemingly bullet proof I finally implemented a switch over to a O(n^2) multiply algorithm. Given that the crossover point is so low, it appears your O(n^2) multiply is rather slow. Upon looking at the code, I see that you are working in base 1E18 and ...
by ejolson
Thu Dec 27, 2018 2:10 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Ah, sorry, that 128 bit maths is still hardwired into the code. I'll fix it. I'm running a 64 bit OS on my Pi which might account for a lot. It looks possible that 128-bit division relative to 64-bit division is faster on a 64-bit Pi compared to a PC. Alternatively, your code might have vectorized ...
by ejolson
Wed Dec 26, 2018 10:45 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Heater wrote:
Wed Dec 26, 2018 10:35 pm
Too much Christmas spirit I think.
After New Year the Christmas festivities should be over. By then maybe some wise guys will arrive bearing gifts of gold, frankincense and FreePascal code optimized with inline NEON assembly.
by ejolson
Wed Dec 26, 2018 9:37 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Well blow me down. Despite being able to calculate fibo(4784969) and despite my fuzzing my karatsuba multiply with a lot of random inputs of all kind of sizes, I find that there were still some magic values of input that cause my big integer subtraction to fail. Good job squashing that bug. I was q...
by ejolson
Tue Dec 25, 2018 12:40 am
Forum: Advanced users
Topic: Historic Unix R7 using SIMH
Replies: 21
Views: 7868

Re: Historic Unix R7 using SIMH

W. H. Heydt wrote:
Mon Dec 24, 2018 5:53 am
Since you were emulating a PDP 11/70, it would be appropriate to use what Berkeley was running on them in the early '70s...bsd 2.9.
That's another option. Have you tried BSD 2.9 on Raspberry Pi using the PDP-11 simulator in SIMH?
by ejolson
Tue Dec 25, 2018 12:28 am
Forum: Advanced users
Topic: Historic Unix R7 using SIMH
Replies: 21
Views: 7868

Re: Historic Unix R7 using SIMH

Many thanks to ejolson for writing this up. I am posting a few minor but crucial edits. Like MaxK1 , I too am trying this on a cold Minnesota day, and I couldn't get the `dz` device working; the `ls -l unix` command returned only 52580 bytes, not 54866. Also, I got an error ` dz: cannot find ` when...
by ejolson
Mon Dec 24, 2018 10:30 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

I cast those doubling formula into javascript. It only improved things by 5% compared to Paeryn's FiboFast style. Since the doubling formulas used by FiboFast have also been simplified to contain only one multiplication each, one would not expect much difference in performance. The remaining 5 perc...
by ejolson
Mon Dec 24, 2018 3:42 am
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Here is another program that uses the doubling formulas to compute Fibonacci numbers. As this program performs big-number addition, subtraction and multiplication using the GNU multi-precision subroutine library, it serves both as a point of comparison for any programming language that uses GMP behi...
by ejolson
Sun Dec 23, 2018 10:20 pm
Forum: Off topic discussion
Topic: Why Avoid BASIC on RPi?
Replies: 2312
Views: 159485

Re: Why Avoid BASIC on RPi?

Now if only I could figure out what your FiboFaster is doing... The updates recently posted to the FreeBASIC code do something similar. Both are based on a way of writing the doubling formula simplified by Cassini's identify to use fewer multiplications. You posted the new formula and I remarked on...

Go to advanced search