ejolson wrote: ↑Tue Jan 15, 2019 8:06 pm

Along those lines, it would be nice if a RISC OS BBC BASIC code (with or without inline assembler) were to appear.

Among such exalted and professional company, dicussing such esoteric matters, what could a dilettante such as myself hope to offer.

Well, here is a plain interpreted fibo program. It must be run using BBC BASIC VI (Basic64) to take advantage of 64-bit floats and the VFP ARM instructions. It does not use Karatsuba multiplication, firstly because I cannot see an economical way to do that and secondly because it would interfere with the whole array multiplication that BASIC provides. There are things that could be tidied up and some very small speed improvements, but without using unofficial trickery on arrays I cannot see any major advances. BBC BASIC is hopeless for this as anyone could predict.

Code: Select all

```
REM> Fibobas
N%=4784969
T%=FNinit(N%):REM intialise and return start time
PROCfibo(N%):REM the main routine
PROCtime(T%):REM report time elapsed since T%
REMPROCprint(a())
PROChead(a(),3):REM show head of fibo
PROCtail(a(),3):REM show tail of fibo
PROCtime(T%):REM report time elapsed since T%
END
REM fast doubling algorithm =====================
DEFPROCfibo(n%)
IF n%=0 THEN
PROClet(a(),0)
PROClet(b(),1)
ELSE
PROCfibo(n%DIV2)
IF n%MOD2=1 THEN PROCodd ELSE PROCeven
ENDIF
ENDPROC
DEFPROCodd
PROCadd(a(),a(),c()):REM c=2a
PROCadd(c(),b(),c()):REM c=2a+b
REMPROCnorm(c())
PROCmul(a(),c(),d()):REM d=a(2a+b)
SWAP a(),d()
IF n%MOD4=1 THEN PROCinc(a()) ELSE PROCdec(a()):REM-(-1)^k
IF n%=N% THEN ENDPROC
PROCmul(b(),c(),d()):REM b=b(2a+b)
SWAP b(),d()
ENDPROC
DEFPROCeven
PROCadd(b(),b(),c()):REM c=2b
PROCsub(c(),a(),c()):REM c=2b-a
PROCnorm(c())
PROCmul(a(),c(),d()):REM d=a(2b-a)
SWAP a(),d()
IF n%=N% THEN ENDPROC
PROCmul(b(),c(),d()):REM b=b(2b-a)
SWAP b(),d()
IF n%MOD4=0 THEN PROCdec(b()) ELSE PROCinc(b()):REM+(-1)^k
ENDPROC
REM big number routines =========================
DEFPROClet(a(),n%):REM assign big num
LOCAL i%
a()=0
WHILE n%
q%=n%/b
a(i%)=n%-b*q%:REM =n%MODb
n%=q%:REM =n%DIVb
i%+=1
ENDWHILE
ENDPROC
DEFPROCinc(a()):REM increment by 1
LOCAL i%
a(0)+=1
WHILE a(i%)>=b:REM only as far as required
a(i%)-=b
a(i%+1)+=1
i%+=1
ENDWHILE
ENDPROC
DEFPROCdec(a()):REM decrement by 1
LOCAL i%
a(0)-=1
WHILE a(i%)<0:REM only as far as required
a(i%)+=b
a(i%+1)-=1
i%+=1
ENDWHILE
ENDPROC
DEFPROCadd(a(),b(),c()):REM not normalised c() ok a() or b()
c()=a()+b()
ENDPROC
DEFPROCsub(a(),b(),c()):REM not normalised c() ok a() or b()
c()=a()-b()
ENDPROC
DEFPROCmul(a(),b(),c()):REM c() not a() or b()
LOCAL h%,i%,j%,q%
h%=FNdigits(n%)DIVe%+1
c()=0
FOR i%=0 TO h%
i()=a()*b(i%)
FOR j%=i% TO h%
c(j%)+=i(j%-i%)
IF c(j%)>=b THEN
q%=c(j%)/b
c(j%+1)+=q%:REM +=c(j%)DIVb
c(j%)-=b*q%:REM =c(j%)MODb
ENDIF
NEXT j%
NEXT i%
ENDPROC
DEFPROCnorm(a()):REM after add/sub only
LOCAL i%
FOR i%=0 TO d%-1
IF a(i%)<0 THEN a(i%+1)-=1:a(i%)+=b
IF a(i%)>=b THEN a(i%+1)+=1:a(i%)-=b
NEXT i%
ENDPROC
REM support routines ============================
DEFFNinit(n%)
LOCAL s%
e%=8:REM exponent of number base using BASIC VI
d%=FNdigits(n%)DIVe%+1:REM dimension of number array
b=10^e%:REM number base
p$=STRING$(e%-1,"0"):REM print prefix
END=&C000+5*d%*8:REM ensure memory
DIM a(d%),b(d%),c(d%),d(d%),i(d%):REM create number arrys
PRINT "Fibo",n%
=TIME:REM start time cs
DEFFNdigits(f%)
=INT(1+f%*LOG((1+SQR5)/2)-LOG5/2)
DEFPROCtime(t%)
LOCAL s%
t%=TIME-t%
s%=t% MOD 6000
PRINT "Time ";t% DIV 6000;":";s% DIV 100;".";s% MOD 100
ENDPROC
DEFPROCprint(a())
LOCAL i%
i%=d%
WHILE a(i%)=0:i%-=1:ENDWHILE:REM ignore leading zeros
PRINT STR$a(i%);:REM first without leading zeros
IF i% THEN
FOR i%=i%-1 TO 0 STEP -1
PRINT RIGHT$(p$+STR$a(i%),e%);:REM with leading zeros
NEXT i%
ENDIF
PRINT
ENDPROC
DEFPROChead(a(),c%)
LOCAL i%
i%=d%
WHILE a(i%)=0:i%-=1:ENDWHILE:REM ignore leading zeros
PRINT STR$a(i%);:REM first without leading zeros
IF i% THEN IF c%>1 THEN
FOR i%=i%-1 TO i%-c%+2 STEP -1
PRINT RIGHT$(p$+STR$a(i%),e%);:REM with leading zeros
NEXT i%
ENDIF
PRINT
ENDPROC
DEFPROCtail(a(),c%)
LOCAL i%
FOR i%=c%-1 TO 0 STEP -1
PRINT RIGHT$(p$+STR$a(i%),e%);:REM with leading zeros
NEXT i%
PRINT
ENDPROC
```

Code: Select all

```
Fibo 4784969
Digits 1000000
107273956418004772293649
801767643812806105156269
Time 263:47.43
```