User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 11:54 am

Heater wrote:
Tue Dec 11, 2018 10:55 am
ejolson,
How, where, when, why, who and at what time will the C++ Fibonacci code be ready?
You know how programming in C++ causes brain seizures, posttraumatic stress disorder, anxiety, depression and paranoia? Among other recorded symptoms up to and including thoughts of suicide.

Well, after a period of relaxation and therapy, and under heavy medication I hope to be back on the job soon.
C++ is the maze of the unthinkable, created to make the line of code counters happy, I thus think.

For a given task, using C++, easier it makes, more lines of code, added.

I will stick with ARM assembly for real work, C for the toys that go accross platforms, BASIC for fun, and machine language to relax.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 11:57 am

PeterO wrote:
Tue Dec 11, 2018 8:22 am
Heater wrote:
Tue Dec 11, 2018 6:57 am
Gavinmc42,
Bah! Young'n's. In the beginning were various Autocodes, then we had FORTRAN and ALGOL, BASIC was the new kid on the block. Actual grumpy old man :)
FIxed it :-)
In the begining there were pathways, then came machine code, then the concept of assembly, then autocodes, and we moved on to the High Level Languages that hold on by a tenuous fine thread, Assembly still ruling them all.

:)
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
Gavinmc42
Posts: 4631
Joined: Wed Aug 28, 2013 3:31 am

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 11:58 am

Whoops must be using 32bit maths, went negative > 2Billion
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

User avatar
Gavinmc42
Posts: 4631
Joined: Wed Aug 28, 2013 3:31 am

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 12:12 pm

Hmm that why Raspbian needs to be 64 bit, 32bit integer only does fibo to 47 loops.
Perhaps BCD maths in assembler?

Davids, you have a funny way to relax, I do it by turning the computers off, night ;)
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

jahboater
Posts: 6099
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 1:34 pm

Heater wrote:
Tue Dec 11, 2018 10:55 am
You know how programming in C++ causes brain seizures, posttraumatic stress disorder, anxiety, depression and paranoia? Among other recorded symptoms up to and including thoughts of suicide.
Well D seems to be moving in that direction too, sadly.
It is now a very big language with many features I have also seen in modern C++.
And, controversially for a systems programming language, it has Garbage Collection :( :(

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

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 1:42 pm

Gavinmc42,
Yep that why I use Free Pascal these days, ...
Excellent. I woke up this morning with the thought that it would be nice to have more contributions to the fibo() challenge in other languages. Pascal came to mind.

So welcome to the challenge and we look forward to what you come up with.

Performance is not the main point here, although the more the better, but rather code readability/understandability is being compared. It should be beautiful.

Entries should not use any external, non-standard, libraries to help. The idea is to see your code do the job.
Whoops must be using 32bit maths, went negative > 2Billion
You will be able to climb a bit higher up the Fibonacci ladder by using unsigned integers. We don't need any signed numbers here.

You will be able to climb a bit further still by using 64 bit unsigned integers. This should still be runnable on a 32 bit machine. It's no problem in C, I forget how Pascal handles 64 bit integers.

However.... the challenge at hand here is to calculate the first Fibonacci number with one million decimal digits. That is fibo(4784969).

You will find inspiration and examples as to how to tackle this here: https://github.com/ZiCog/fibo_4784969
Davids, you have a funny way to relax, I do it by turning the computers off, night
One should never turn computers off. It's cruel.

Not a funny way at all. Some of the most magical communing with computers when programming happens after midnight. That quite time when there is little to disturb ones thoughts.
Memory in C++ is a leaky abstraction .

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

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 2:01 pm

DavidS,
...ease of use and programming that RISC OS and ARM Assembly bring to the table...
I think, in view of your endless claims that programming in assembler is easier you should abandon your abandon your efforts at fibo(4784969) in any BASIC and present your solution in assembler.

After all we already have a BASIC solution in FreeBASIC by ejolson by which to compare readbilty/understandability.

I would only request that your assembler solution be buildable on a Raspberry Pi running Raspbian so that the most people can appreciate it.

I look forward to your contribution.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 6099
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 2:12 pm

David,

I know you don't like the standard ARM assembly languages, but ....
I recently spotted that the "as" assembler supports everything from ARMv1. I presume that's including 26-bit mode as well!
mcpu=processor[+extension…]

This option specifies the target processor. The assembler will issue an error message if an attempt is made to assemble an instruction which will not execute on the target processor. The following processor names are recognized: arm1, arm2, arm250, arm3, arm6, arm60, arm600, arm610, arm620, arm7, arm7m, arm7d, arm7dm, arm7di, arm7dmi, arm70, arm700, arm700i, arm710, arm710t, arm720, arm720t, arm740t, arm710c, arm7100, arm7500, arm7500fe, arm7t, arm7tdmi, arm7tdmi-s, arm8, arm810, strongarm, strongarm1, strongarm110, strongarm1100, strongarm1110, arm9, arm920, arm920t, arm922t, arm940t, arm9tdmi, fa526 (Faraday FA526 processor), fa626 (Faraday FA626 processor), arm9e, arm926e, arm926ej-s, arm946e-r0, arm946e, arm946e-s, arm966e-r0, arm966e, arm966e-s, arm968e-s, arm10t, arm10tdmi, arm10e, arm1020, arm1020t, arm1020e, arm1022e, arm1026ej-s, fa606te (Faraday FA606TE processor), fa616te (Faraday FA616TE processor), fa626te (Faraday FA626TE processor), fmp626 (Faraday FMP626 processor), fa726te (Faraday FA726TE processor), arm1136j-s, arm1136jf-s, arm1156t2-s, arm1156t2f-s, arm1176jz-s, arm1176jzf-s, mpcore, mpcorenovfp, cortex-a5, cortex-a7, cortex-a8, cortex-a9, cortex-a15, cortex-a17, cortex-a32, cortex-a35, cortex-a53, cortex-a55, cortex-a57, cortex-a72, cortex-a73, cortex-a75, cortex-r4, cortex-r4f, cortex-r5, cortex-r7, cortex-r8, cortex-r52, cortex-m33, cortex-m23, cortex-m7, cortex-m4, cortex-m3, cortex-m1, cortex-m0, cortex-m0plus, exynos-m1, marvell-pj4, marvell-whitney, xgene1, xgene2, ep9312 (ARM920 with Cirrus Maverick coprocessor), i80200 (Intel XScale processor) iwmmxt (Intel(r) XScale processor with Wireless MMX(tm) technology coprocessor) and xscale. The special name all may be used to allow the assembler to accept instructions valid for any ARM processor.
The following architecture names are recognized: armv1, armv2, armv2a, armv2s, armv3, armv3m, armv4, armv4xm, armv4t, armv4txm, armv5, armv5t, armv5txm, armv5te, armv5texp, armv6, armv6j, armv6k, armv6z, armv6kz, armv6-m, armv6s-m, armv7, armv7-a, armv7ve, armv7-r, armv7-m, armv7e-m, armv8-a, armv8.1-a, armv8.2-a, armv8.3-a, armv8-r, armv8.4-a, iwmmxt iwmmxt2 and xscale.
Again, you may not like "as", but you have to admit that's pretty complete coverage. I will be impressed if ObjAsm covers all these.

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 2:25 pm

jahboater wrote:
Tue Dec 11, 2018 2:12 pm
David,

I know you don't like the standard ARM assembly languages, but ....
I recently spotted that the "as" assembler supports everything from ARMv1. I presume that's including 26-bit mode as well!
mcpu=processor[+extension…]

This option specifies the target processor. The assembler will issue an error message if an attempt is made to assemble an instruction which will not execute on the target processor. The following processor names are recognized: arm1, arm2, arm250, arm3, arm6, arm60, arm600, arm610, arm620, arm7, arm7m, arm7d, arm7dm, arm7di, arm7dmi, arm70, arm700, arm700i, arm710, arm710t, arm720, arm720t, arm740t, arm710c, arm7100, arm7500, arm7500fe, arm7t, arm7tdmi, arm7tdmi-s, arm8, arm810, strongarm, strongarm1, strongarm110, strongarm1100, strongarm1110, arm9, arm920, arm920t, arm922t, arm940t, arm9tdmi, fa526 (Faraday FA526 processor), fa626 (Faraday FA626 processor), arm9e, arm926e, arm926ej-s, arm946e-r0, arm946e, arm946e-s, arm966e-r0, arm966e, arm966e-s, arm968e-s, arm10t, arm10tdmi, arm10e, arm1020, arm1020t, arm1020e, arm1022e, arm1026ej-s, fa606te (Faraday FA606TE processor), fa616te (Faraday FA616TE processor), fa626te (Faraday FA626TE processor), fmp626 (Faraday FMP626 processor), fa726te (Faraday FA726TE processor), arm1136j-s, arm1136jf-s, arm1156t2-s, arm1156t2f-s, arm1176jz-s, arm1176jzf-s, mpcore, mpcorenovfp, cortex-a5, cortex-a7, cortex-a8, cortex-a9, cortex-a15, cortex-a17, cortex-a32, cortex-a35, cortex-a53, cortex-a55, cortex-a57, cortex-a72, cortex-a73, cortex-a75, cortex-r4, cortex-r4f, cortex-r5, cortex-r7, cortex-r8, cortex-r52, cortex-m33, cortex-m23, cortex-m7, cortex-m4, cortex-m3, cortex-m1, cortex-m0, cortex-m0plus, exynos-m1, marvell-pj4, marvell-whitney, xgene1, xgene2, ep9312 (ARM920 with Cirrus Maverick coprocessor), i80200 (Intel XScale processor) iwmmxt (Intel(r) XScale processor with Wireless MMX(tm) technology coprocessor) and xscale. The special name all may be used to allow the assembler to accept instructions valid for any ARM processor.
The following architecture names are recognized: armv1, armv2, armv2a, armv2s, armv3, armv3m, armv4, armv4xm, armv4t, armv4txm, armv5, armv5t, armv5txm, armv5te, armv5texp, armv6, armv6j, armv6k, armv6z, armv6kz, armv6-m, armv6s-m, armv7, armv7-a, armv7ve, armv7-r, armv7-m, armv7e-m, armv8-a, armv8.1-a, armv8.2-a, armv8.3-a, armv8-r, armv8.4-a, iwmmxt iwmmxt2 and xscale.
Again, you may not like "as", but you have to admit that's pretty complete coverage. I will be impressed if ObjAsm covers all these.
I do like the standard, as in the syntax introduced originally by the people who made the ARM, and the syntax used by most ARM programmers for a long time thereafter.

I do not like the GAS syntax.

As a note any 32-bit ARM assembler can produce code for the ARMv1, just make sure you do not use anything that came later.

For a good ARM Assembler on Linux, take a look at asasm, it uses the standard Acorn format, and works well. Unfortunately you will have to recompile it, though that is not a big issue.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

jahboater
Posts: 6099
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 2:34 pm

DavidS wrote:
Tue Dec 11, 2018 2:25 pm
I do not like the GAS syntax.
Don't forget that gas doesn't have any syntax of its own. UAL, A32, A64 etc etc come from ARM, not from gas.
If you don't like the syntax, then it means you don't like standard ARM assembler syntax. Its not gas's fault!!!!
In ARM's own words:- "the preferred architectural assembly language notation".

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 2:43 pm

Heater wrote:
Tue Dec 11, 2018 2:01 pm
DavidS,
...ease of use and programming that RISC OS and ARM Assembly bring to the table...
I think, in view of your endless claims that programming in assembler is easier you should abandon your abandon your efforts at fibo(4784969) in any BASIC and present your solution in assembler.

After all we already have a BASIC solution in FreeBASIC by ejolson by which to compare readbilty/understandability.

I would only request that your assembler solution be buildable on a Raspberry Pi running Raspbian so that the most people can appreciate it.

I look forward to your contribution.
Really, I get to do it the easy way. KOOL :) :) :) .

And making it Linux compatible is not an issue, I just need to write it to assemble with asasm and have a conditional assembly, so when assembled on Linux it uses:

Code: Select all

  ADR R1,Buff
  MOV R0,#1
  MOV R2,#seclen
  SWI &900004
output each section of text in Linux.

On RISC OS I would use:

Code: Select all

  ADR R0, Buff
  SWI &02
To perform the output of a null terminated ASCII string.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 3:01 pm

DavidS,
Really, I get to do it the easy way. KOOL
Yay, go for it !
Memory in C++ is a leaky abstraction .

jahboater
Posts: 6099
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 3:11 pm

The file write system call on Linux 32-bit looks like this:-

Code: Select all

     MOV R0,#1    // file descriptor
     ADR R1,Buff  // message string
     MOV R2,#12   // length
     MOV R7,#4    // SYS_write
     SWI 0        // same as SVC 0
The return code is in R0 (number of bytes written on success, otherwise "errno" negated)

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 3:23 pm

jahboater wrote:
Tue Dec 11, 2018 3:11 pm
The file write system call on Linux 32-bit looks like this:-

Code: Select all

     MOV R0,#1    // file descriptor
     ADR R1,Buff  // message string
     MOV R2,#12   // length
     MOV R7,#4    // SYS_write
     SWI 0        // same as SVC 0
The return code is in R0 (number of bytes written on success, otherwise "errno" negated)
That is for EABI, as the kernel still supports OABI (thank you Linus), I posted the OABI version of SYS_write which I will be using (as well as the OABI for SYS_exit using SWI &900001 with error in R0).

I do not like EABI because it conflicts with the RISC OS call OS_WriteC (SWI 0) and thus makes mixing the two OS's running together rather difficult (not to mention limits the usefulness of trapping errors to determine which OS you are running on). And this is even more important now that someone is finally getting us a RISC OS on Linux implementation up and running.

BTW in traditional assemblers like asasm the & prefix indicates a hexadecimal number. It also supports the 0x prefix if people are more comfortable with that.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 4:49 pm

The interesting irony. At long last AROS native booting on the RPi in a usable form is nearly here. C is to Amiga OS as Assembly is to RISC OS, ACE BASIC is to Amiga OS as ARM BASIC is to RISC OS. And even assembly is fun on Amiga OS/AROS. AROS is the modern form for Amiga OS, as the original is no more updated, while AROS is a truly modern OS in all ways (thanks to Amiga OS, on which AROS is modeled, being way ahead of its time).

I finally get to have fun, going to be spending more time with my Amiga 1200 to make sure I am completely familiar with the Amiga API still, as well as the CLI (which is mostly inherited from TripOS).

It is a fusion of the two best things, AROS and affordable ARM, that is finally coming to pass. It may be frame buffer for now though it should not be long before VideoCoreIV support is implemented in AROS, as it makes it easier than with many other OS's to add the support.

I am very much looking forward to using AROS as my main OS (though I am going to have to get RPCEmu running on it so I still have RISC OS) on an affordable ARM based system.

The point to this topic is that there should be at least one compiler that is compatible with ACE Basic available for AROS, may have to retarget for ARM though that is alright. I have always liked that dialect of BASIC even before ACE came out (it started with the poorly done AmigaBASIC interpreter from MS, so is very similar to QB/PDS on other systems, though has full GUI features, and with ACE includes structures in a reasonable way).
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

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

Re: Why Avoid BASIC on RPi?

Tue Dec 11, 2018 7:23 pm

Heater wrote:
Tue Dec 11, 2018 2:01 pm
After all we already have a BASIC solution in FreeBASIC by ejolson by which to compare readbilty/understandability.
Unfortunately, the FreeBASIC solution is not complete as it is missing the Karatsuba multiplication routine. I had been hoping some other BASIC enthusiast would finish it. Do you need a break from C++?

User avatar
Gavinmc42
Posts: 4631
Joined: Wed Aug 28, 2013 3:31 am

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 1:27 am

You will be able to climb a bit further still by using 64 bit unsigned integers. This should still be runnable on a 32 bit machine. It's no problem in C, I forget how Pascal handles 64 bit integers.
Me too, had to Google,
Integer seems to default to 32bit in Free Pascal, i = int64 is what is needed.
That obviously will not get fibo to a million places either.
Thanks for the ZiCog link, I'm still playing catchup.

Is it cheating if I use NEON?
That was the whole point of me getting an Aarch64 Pi and Pascal compiler.

Wonder what integers SmartBasic uses on the BT 5.0 module?
Faster than Spin on the Prop?
One should never turn computers off. It's cruel.
No it is cruel to leave them on doing nothing.
Without input it is like solitary confinement for a million years.
Besides they might evolve overnight and take over, you have to watch them carefully these days.
The "Spike" could happen at anytime now.

Now if you were a Computer what language would you choose to evolve with?
Assembler and Basic seems like devolution, sticking with them might just save us?
Python is used a lot with AI/Neural network stuff, could Basic do it too?
Are we handicapping computers by using people based languages?
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

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

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 2:16 am

Gavinmc42,

If NEON helps why not. But as long as it does not show up in your source as some funky assembler. That is not Pascal.
No it is cruel to leave them on doing nothing.
Oh this machine has a lot to do.

Chatting to it's many friends at Microsoft, fetching updates, talking about what I have been doing all day.

And it's other friends at Google and elsewhere that like to know what we are up to.

This machine has a better social life than I do !
Memory in C++ is a leaky abstraction .

User avatar
Gavinmc42
Posts: 4631
Joined: Wed Aug 28, 2013 3:31 am

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 6:01 am

If NEON helps why not. But as long as it does not show up in your source as some funky assembler. That is not Pascal.
If Pascal allows inline assembly then it is allowed?

Code: Select all

var
 Value:LongWord;
begin
 Value:=Parameter;
 
 asm
  ldr r0, Value
  add r0, r0, #123
  str r0, Value
 end;
 
 Result:=Value;
end;
All good languages should allow inline asm, if they don't they are not good enough ;)
I don't remember Basic allowing asm, but it was so long ago since I have used any Basic.

Heater don't let your computer out at night, it could catch a horrible disease that may require quarantine or brain transplant.
I stopped using Windows when I could not stop my PCs from straying or upgrading someone else's PC.
They are much more obedient now on Linux Mint.
And lets face it if we comment on here we both probably should be getting out more
Or perhaps even talking to biological lifeforms like the wife and kids.
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

jahboater
Posts: 6099
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 7:55 am

Gavinmc42 wrote:
Wed Dec 12, 2018 6:01 am
All good languages should allow inline asm, if they don't they are not good enough ;)
I don't remember Basic allowing asm, but it was so long ago since I have used any Basic.
I believe BBC Basic can, and I thought older Basic's could execute stuff presented in hex in comments.

Only C can do this though (which is relevant for the bignum arithmetic):

Code: Select all

unsigned int value;
bool carry;
         
asm( "add %0,123" : "+r" (value), "=@ccc" (carry) );

if( carry )
  puts( "addition sets the carry bit!" );
which here does "add" followed by "jnc".

C is the only language to handle the CPU flags in the users code without saving the flag in a variable.
And "probably" the only language to allow inline asm code to fully participate in the surrounding optimization.

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

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 8:59 am

Heater wrote:
Wed Dec 12, 2018 2:16 am
If NEON helps why not. But as long as it does not show up in your source as some funky assembler. That is not Pascal.
From my point of view the present project compares the expressiveness of Basic to other programming languages by measuring in each language how efficiently the Karatsuba multiplication algorithm can be coded and then used to compute the 4784969th Fibonacci number by means of the doubling formulas. While I suspect no one would mind if you coded a Fourier-transform based big-number multiplication and instead used some sort of tripling formula, one of the advantages of a high-level programming language as opposed to assembler, in my opinion, is that the code can run on different CPU architectures without change. Inline assembler has its uses, but in this comparison such efforts would reflect the expressiveness of assembler and not Pascal

As the Raspberry Pi is intended for use in an educational setting, how clearly a programming language allows an algorithm to be coded is important. However, when teaching the advantages of Karatsuba multiplication or trying to learn it, it is important that the programming language also allow for an efficient enough implementation that problems can be sized in the asymptotic regime where the O(n^1.58) runtime wins over simpler O(n^2) algorithms. Thus, sufficient execution speed is necessary from a practical viewpoint.

While students are notably more practical than their teachers, being able to implement personal algorithms that make efficient use of computer hardware also liberates an individual from the constraints of existing subroutine libraries and built-in functionality--an essential step towards digital enlightenment.

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

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 10:27 am

Yay!

The fibo kartasuba in C++ finally works. Yabba dabba dodda!

Code: Select all

$ g++ -Wall -O3 -o fibo_karatsba fibo_karatsba.cpp bint.cpp -I.
$ time ./fibo_karatsba | head  -c 32
00000000107273956418004772293648
real    1m37.786s
user    1m37.531s
sys     0m0.047s

$ time ./fibo_karatsba | tail  -c 32
4856539211500699706378405156269

real    1m37.490s
user    1m37.313s
sys     0m0.078s
Here is the top level code:

Code: Select all

#include <bint.h>
#include <time.h> 

bint zero = "0";
bint one = "1";
bint two = "2";

bint memo[] = {zero, one, one};

int isEven(int n)
{
    return (n & 1) == 0;
}

bint fibo (int n)
{
    if (n <= 2)
    {
        return memo[n];
    }
    else
    {
        int k = (n / 2);
        bint fk = fibo(k);
        bint fk1 = fibo(k + 1);
        if (isEven(n))
        {
            return fk * (fk1 * two - fk);
        }
        return (fk * fk) + (fk1 * fk1);
    }
}

int main (int argc, char* argv[])
{
    bint res = fibo(4784969);

    std::cout << res << std::endl;
    return 0;
}
In terms of expressiveness I think it's gorgeous. It spells out the fast fibo algorithm as clearly as the Python or Javascript versions. DavidS should be happy, it looks just like C does it not? Except for that mysterious "bint" data type.

Same expressiveness is holds for the karatsuba multiply algorithm. Which closely resembles the pseudo code on Wikipedia:

Code: Select all

bint bint::mul (const bint& b)
{
    // The base case(s), only one element in value, just do the multiply
    if (width == 1)
    {
        return b.simpleMul(value[0]);
    }
    if (b.width == 1)
    {
        return simpleMul(b.value[0]);
    }
    // Calculates the size of the numbers
    int m = (this->width);
    int m2 = m / 2;

    // Split the numbers in the middle
    bint high1 = this->high(m2);
    bint low1 = this->low(m2);
    bint high2 = b.high(m2);
    bint low2 = b.low(m2);

    // Do da karatsaba shuffle, yabba dabba do.
    bint z0 = low1 * low2;
    bint z1 = (low1 + high1) * (low2 + high2);
    bint z2 = high1 * high2;

    bint s1 = z1 - z2;
    bint s2 = s1 - z0;

    return  z2.shift(m2 * 2) + s2.shift(m2) + z0;
}
Of course... things are a bit more involved under the hood of that mysterious bint type. The code is here: https://github.com/ZiCog/fibo_4784969/b ... B/bint.cpp for your perusal and comment.

But what about performance?

Well, it sucks. On this PC it's about 60 times slower than ejolson's C version. On the other hand it's over 3 times faster than the karatsuba in javascript version and uses 10 times less memory!

Hardly surprising seeing as I'm naively new'ing and free'ing all over the space for intermediate big integer values and there is a lot of array copying going on. I have to see what I can do about that.

Interestingly my C++ version is only a few source lines more than ejolson's C version, 261 vs 289. So much for DavidS' claims about C++ requiring a lot more lines of code.
Memory in C++ is a leaky abstraction .

User avatar
Gavinmc42
Posts: 4631
Joined: Wed Aug 28, 2013 3:31 am

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 10:49 am

I will achieve digital enlightenment once I figure out what Karatsuba multiplication is ;)
I now know enough that just adding numbers in even 64bit will not be enough.

Big number stuff, google time, that memory is too old to recover quickly.
Somewhere I have 6805 BCD calculator code in C on a 5 1/4 floppy.
Floats were not good enough for recursive calcs of solar and lunar orbits for tides.
Ok, I will stick to pure Free Pascal, that compiles on lots of CPUs these days, even Microbits?.

bint for Big Integers?
That C++ looks translatable to Pascal,
Wonder if I can do it without coffee?
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

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

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 11:59 am

It could be "bint", the Arabic word for girl/daughter. It could be "bint", the British English derogatory term for girl or woman. Or it could be "bint" short for "big integer".

I might just be being a bit playful there.

If your Pascal has objects it should translate easy enough.

I'm not keen on seeing inline assembler. The whole discussion of this thread is about language readability and expressiveness. If you throw assembler into your Pascal that is no longer Pascal we are looking at. And we can't build and run it on other machines.
Memory in C++ is a leaky abstraction .

User avatar
DavidS
Posts: 4334
Joined: Thu Dec 15, 2011 6:39 am
Location: USA
Contact: Website

Re: Why Avoid BASIC on RPi?

Wed Dec 12, 2018 12:42 pm

jahboater wrote: C is the only language to handle the CPU flags in the users code without saving the flag in a variable.
And "probably" the only language to allow inline asm code to fully participate in the surrounding optimization.
Actually C can not, not while following the standard. what you are talking about is implementation specific extensions to the language.

C is the only language that does not specify how to implement inline assembly, leaving us with different implementations that are incompatible on the same CPU. And the gcc implementation putting assembly in quoted strings is likely the worse C implementation of ASM to read of them all.

The asm keyword is explicitly implementation defined. So we can have no standard way of it, as there are already way to many ways used by C compilers.
RPi = The best ARM based RISC OS computer around
More than 95% of posts made from RISC OS on RPi 1B/1B+ computers. Most of the rest from RISC OS on RPi 2B/3B/3B+ computers

Return to “Off topic discussion”