A good question for the Raspberry Pi Foundation.ejolson wrote: ↑Fri Nov 08, 2019 6:32 pmAre you sure you don't have any 8GB Pi 4B computers you would like to donate?John_Spikowski wrote: ↑Fri Nov 08, 2019 6:22 pmI'm giving a free copy of ScriptBasic away to anyone coming up with correct answer.
Code: Select all
' Tatami.sb
nMax = 6700000
nMaxSqrt = SQR(nMax)
SPLITA STRING(nMax, "0") BY "" TO v
FUNCTION Tatami(s)
FOR i = 7 TO nMaxSqrt STEP 2
k2 = i + 3
k3 = i + i - 4
WHILE (k2 <= k3) AND ((i * k2) < nMax)
k4 = nMax / i
IF k3 < k4 THEN
k4 = k3
END IF
FOR j = k2 TO k4 STEP 2
v[i * j] += 1
NEXT
k2 += i + 1
k3 += i - 1
WEND
NEXT
FOR i = 8 TO nMaxSqrt STEP 2
k2 = 1 + 3
k3 = i + i - 4
WHILE (k2 <= k3) AND ((I * k2) < nMax)
k4 = nMax / i
IF k3 < k4 THEN
k4 = k3
END IF
FOR j = k2 TO k4
v[i * j] += 1
NEXT
k2 += i + 1
k3 += i - 1
WEND
NEXT
FOR i = 0 TO nMax
IF v[i] = s THEN
Tatami = i
EXIT FUNCTION
END IF
NEXT
END FUNCTION
s = 100
PRINT FORMAT("The smallest room size s for which T(s) = %d is %d\n", s, Tatami(s))
Code: Select all
[email protected]:~/sb/tatami$ scriba Tatami_Final.sb
The smallest room size s for which T(s) = 100 is 240240
[email protected]:~/sb/tatami$
If you use integer division or something like INT(nMax/i) does it work?John_Spikowski wrote: ↑Sat Nov 09, 2019 1:26 amI'm still getting the same wrong answer with the new updated code.
Code: Select all
' Tatami.sb nMax = 6700000 nMaxSqrt = SQR(nMax) SPLITA STRING(nMax, "0") BY "" TO v FUNCTION Tatami(s) FOR i = 7 TO nMaxSqrt STEP 2 k2 = i + 3 k3 = i + i - 4 WHILE (k2 <= k3) AND ((i * k2) < nMax) k4 = nMax / i IF k3 < k4 THEN k4 = k3 END IF FOR j = k2 TO k4 STEP 2 v[i * j] += 1 NEXT k2 += i + 1 k3 += i - 1 WEND NEXT FOR i = 8 TO nMaxSqrt STEP 2 k2 = 1 + 3 k3 = i + i - 4 WHILE (k2 <= k3) AND ((I * k2) < nMax) k4 = nMax / i IF k3 < k4 THEN k4 = k3 END IF FOR j = k2 TO k4 v[i * j] += 1 NEXT k2 += i + 1 k3 += i - 1 WEND NEXT FOR i = 0 TO nMax IF v[i] = s THEN Tatami = i EXIT FUNCTION END IF NEXT END FUNCTION s = 100 PRINT FORMAT("The smallest room size s for which T(s) = %d is %d\n", s, Tatami(s))
Code: Select all
[email protected]:~/sb/tatami$ scriba Tatami_Final.sb The smallest room size s for which T(s) = 100 is 240240 [email protected]:~/sb/tatami$
I think it would be better to check the C code first. Compared to the original, the present code has apparently been optimised to skip the odd products i*j which aren't needed for finding the answer. I wonder if a bug crept into the program during the optimisation.John_Spikowski wrote: ↑Sat Nov 09, 2019 2:34 amNo help. I tried that early on.
You only need scriba to run this.
Code: Select all
[email protected]:~/sbrt/examples $ time ./tatami 100
The smallest room size s for which T(s) = 100 is 6683040
real 0m12.668s
user 0m12.319s
sys 0m0.340s
[email protected]:~/sbrt/examples $ time ./tatami 200
The smallest room size s for which T(s) = 200 is 85765680
real 0m13.085s
user 0m12.677s
sys 0m0.400s
[email protected]:~/sbrt/examples $
The T(s)=100 calculation using cbmbasic on the Raspberry Pi 4B just finished.
Code: Select all
$ time cbmbasic PETAMI.BAS
T( 6683040 )= 100
real 1553m55.704s
user 1553m53.570s
sys 0m0.711s
Code: Select all
' vtat.sb -- ScriptBasic translation of Eric Olson's VB code.
SUB Tinit(n)
s_max = n - 1
i_max = SQR(s_max) + 0.5
SPLITA STRING(n, "0") BY "" TO T
FOR i = 1 TO i_max
j_min = i + 3
j_max = 2 * i - 4
WHILE i * j_min <= s_max AND j_min <= j_max
FOR j = j_min TO j_max
IF i * j <= s_max THEN
T[i * j] = T[i * j] + 1
END IF
NEXT
j_min = j_min + i + 1
j_max = j_max + i - 1
WEND
NEXT
END SUB
FUNCTION Tinv(n)
FOR s = 2 TO s_max STEP 2
IF T[s] = n THEN
Tinv = s
EXIT FUNCTION
END IF
NEXT
Tinv = -1
END FUNCTION
Tinit(6700000)
PRINT FORMAT("T(%d) = 100", Tinv(100)),"\n"
Code: Select all
[email protected]:~/sbrt/examples $ time scriba vtat.sb
T(6683040) = 100
real 1m40.526s
user 1m37.712s
sys 0m2.467s
[email protected]:~/sbrt/examples $
Code: Select all
[email protected]:~/sbrt/examples $ time scriba Tatami_Final.sb
The smallest room size s for which T(s) = 100 is 240240
real 0m50.098s
user 0m48.135s
sys 0m1.949s
[email protected]:~/sbrt/examples $
Code: Select all
$ time ./recurse
T(30240)=20
real 3:45.0
user 3:43.9
sys 0.1
Code: Select all
/* recurse.c -- Compute T(s) from Project Euler Problem 256
Written November 8, 2019 by Eric Olson in K&R C for PDP-11
Less copying, more multiplication less division. */
#include <stdio.h>
/*
#define smax 100000000l
#define Pnum 1300
*/
#define smax 40000l
#define Pnum 60
#define fnum 10
typedef struct { long s; int fmax,i; long p[fnum]; char n[fnum]; } factors;
static factors x;
static int Pn,Tisn;
static long P[Pnum],smin;
static char z[fnum];
#define void int
static int tfree(k,l) long k,l; {
long n=l/k;
long lmin=(k+1)*n+2;
long lmax=(k-1)*(n+1)-2;
return lmin<=l && l<=lmax;
}
static long isprime(p) long p;{
int i;
for(i=0;i<Pn;i++){
if(!(p%P[i])) return 0;
}
return 1;
}
static void doinit(){
int i;
long p,r;
smin=smax+2;
P[0]=2; Pn=1;
for(p=3;Pn<Pnum;p++){
if(isprime(p)) P[Pn++]=p;
}
if(p<=smax/p+1){
printf("The maximum prime %ld is too small!\n",p);
exit(1);
}
r=1;
for(i=0;i<fnum-1;i++) {
if(P[i]>smax/r+1) return;
r*=P[i];
}
printf("Distinct primes %d in factorisation too few!\n",fnum);
exit(2);
}
static long ppow(p,n) long p; char n; {
long r;
if(!n) return 1;
r=1;
for(;;){
if(n&1) r*=p;
n>>=1;
if(!n) return r;
p*=p;
}
}
static long T(){
int r,w;
for(w=0;w<fnum;w++) z[w]=0;
r=0;
for(;;){
int i;
long k,l;
for(i=0;i<=x.fmax;i++){
if(z[i]<x.n[i]){
z[i]++; break;
}
z[i]=0;
}
if(i>x.fmax) break;
k=1; l=1;
for(i=0;i<=x.fmax;i++){
k*=ppow(x.p[i],z[i]);
l*=ppow(x.p[i],x.n[i]-z[i]);
}
if(k<=l) r+=tfree(k,l);
}
return r;
}
static void Twork(){
int i,r;
long s,fmax,pmax,p;
s=x.s;
r=T();
if(r==Tisn&&s<smin) smin=s;
i=x.i;
fmax=x.fmax;
pmax=smax/s+1;
p=P[i];
if(p<=pmax){
x.n[fmax]++; x.s=s*p;
Twork();
x.n[fmax]--;
}
fmax++;
x.n[fmax]=1;
for(i++;i<Pnum;i++){
p=P[i];
if(p>pmax) break;
x.p[fmax]=p; x.s=s*p;
x.i=i; x.fmax=fmax;
Twork();
}
x.n[fmax]=0;
}
static long Tinv(n) int n; {
Tisn=n;
x.p[0]=P[0]; x.n[0]=1; x.i=0; x.s=2; x.fmax=0;
Twork();
return smin<smax?smin:-1;
}
int main(){
int n=20;
doinit();
printf("T(%ld)=%d\n",Tinv(n),n);
return 0;
}
Those DECwriters always made me nervous when, after a few seconds, they moved the print head out of the way so it's possible to read what was just typed. Do you still have one?John_Spikowski wrote: ↑Sat Nov 09, 2019 5:15 amThe only thing that looks familiar is the DEC Writer. I bought one with my Heathkit PDP-11 I built.
No. I ran my code on Miss Piggy remotely by logging in over the Internet.
Wish I kept it but it was lost under the no touch in two years it's gone rule.Those DECwriters always made me nervous when, after a few seconds, they moved the print head out of the way so it's possible to read what was just typed. Do you still have one?
Maybe I should start up Soviet built PDP-11 compatible UKNC computer running RT-11 operating system and try running the tatami code....
Here you are John , thanks for letting me keep my scalp!John_Spikowski wrote: ↑Sat Nov 09, 2019 7:27 amHas anyone tried running the ScriptBasic code I posted? Find the problem with Tatami_Final.sb and I will give you a coupon for scalp protection.
Code: Select all
' Tatami.sb
nMax = 6700000
nMaxSqrt = INT(SQR(nMax))
SPLITA STRING(nMax, "0") BY "" TO v
FUNCTION Tatami(s)
FOR i = 7 TO nMaxSqrt - 1 STEP 2
k2 = i + 3
k3 = i + i - 4
WHILE (k2 <= k3) AND ((i * k2) < nMax)
k4 = INT(nMax / i)
IF k3 < k4 THEN
k4 = k3
END IF
FOR j = k2 TO k4 STEP 2
v[i * j] += 1
NEXT
k2 += i + 1
k3 += i - 1
WEND
NEXT
FOR i = 8 TO nMaxSqrt - 1 STEP 2
k2 = i + 3
k3 = i + i - 4
WHILE (k2 <= k3) AND ((i * k2) < nMax)
k4 = INT(nMax / i)
IF k3 < k4 THEN
k4 = k3
END IF
FOR j = k2 TO k4
v[i * j] += 1
NEXT
k2 += i + 1
k3 += i - 1
WEND
NEXT
FOR i = 0 TO nMax - 1
IF v[i] = s THEN
Tatami = i
EXIT FUNCTION
END IF
NEXT
END FUNCTION
s = 100
PRINT FORMAT("The smallest room size s for which T(s) = %d is %d\n", s, Tatami(s))
Don't get bored with computer architectures.. Get into RISC VIt has gotten rather boring since, with only 2 architectures (ARM & X86) left competing for dominance.
The dog developer came bouncing through the door, tail wagging, fully recovered. What's up, I asked. Fido barked, the FidoBasic project has been reinstated! Not only did Scratch fail the latest ADA compliance tests but it is not suitable for literate programming. The only provision to receive full funding is to make a RISC-V version and drop the use of irrational line numbers for n-level meta programming. I looked at Fido, isn't meta programming one of the main features? It is, growled the dog, but I've decided to denote it using quotation marks like everyone else.ejolson wrote: ↑Sat Nov 09, 2019 5:08 amAfter a little editing I obtained the outputin 3 minutes 45 secondsCode: Select all
$ time ./recurse T(30240)=20 real 3:45.0 user 3:43.9 sys 0.1
Code: Select all
$ time ./limited
T(30240)=20
real 1:52.0
user 1:51.5
sys 0.1
Code: Select all
/* limited.c -- Compute T(s) from Project Euler Problem 256
Written November 9, 2019 by Eric Olson in K&R C for PDP-11
Less copying, more multiplication less division.
Avoid computing T(s) when s doesn't have enough factors. */
#include <stdio.h>
/*
#define smax 100000000l
#define Pnum 1300
*/
#define smax 40000l
#define Pnum 60
#define fnum 10
typedef struct { long s; int fmax,i; long p[fnum]; char n[fnum]; } factors;
static factors x;
static int Pn,Tisn;
static long P[Pnum],smin;
static char z[fnum];
#define void int
static int tfree(k,l) long k,l; {
long n=l/k;
long lmin=(k+1)*n+2;
long lmax=(k-1)*(n+1)-2;
return lmin<=l && l<=lmax;
}
static long isprime(p) long p;{
int i;
for(i=0;i<Pn;i++){
if(!(p%P[i])) return 0;
}
return 1;
}
static void doinit(){
int i;
long p,r;
smin=smax+2;
P[0]=2; Pn=1;
for(p=3;Pn<Pnum;p++){
if(isprime(p)) P[Pn++]=p;
}
if(p<=smax/p+1){
printf("The maximum prime %ld is too small!\n",p);
exit(1);
}
r=1;
for(i=0;i<fnum-1;i++) {
if(P[i]>smax/r+1) return;
r*=P[i];
}
printf("Distinct primes %d in factorisation too few!\n",fnum);
exit(2);
}
static long ppow(p,n) long p; char n; {
long r;
if(!n) return 1;
r=1;
for(;;){
if(n&1) r*=p;
n>>=1;
if(!n) return r;
p*=p;
}
}
static long sigma2(){
int i;
long r=x.n[0];
for(i=1;i<=x.fmax;i++) r*=x.n[i]+1;
return r;
}
static long T(){
int r,w;
for(w=0;w<fnum;w++) z[w]=0;
r=0;
for(;;){
int i;
long k,l;
for(i=0;i<=x.fmax;i++){
if(z[i]<x.n[i]){
z[i]++; break;
}
z[i]=0;
}
if(i>x.fmax) break;
k=1; l=1;
for(i=0;i<=x.fmax;i++){
k*=ppow(x.p[i],z[i]);
l*=ppow(x.p[i],x.n[i]-z[i]);
}
if(k<=l) r+=tfree(k,l);
}
return r;
}
static void Twork(){
int i,r;
long s,fmax,pmax,p;
s=x.s;
r=sigma2();
if(r>=Tisn){
r=T();
if(r==Tisn&&s<smin) smin=s;
}
i=x.i;
fmax=x.fmax;
pmax=smax/s+1;
p=P[i];
if(p<=pmax){
x.n[fmax]++; x.s=s*p;
Twork();
x.n[fmax]--;
}
fmax++;
x.n[fmax]=1;
for(i++;i<Pnum;i++){
p=P[i];
if(p>pmax) break;
x.p[fmax]=p; x.s=s*p;
x.i=i; x.fmax=fmax;
Twork();
}
x.n[fmax]=0;
}
static long Tinv(n) int n; {
Tisn=n;
x.p[0]=P[0]; x.n[0]=1; x.i=0; x.s=2; x.fmax=0;
Twork();
return smin<smax?smin:-1;
}
int main(){
int n=20;
doinit();
printf("T(%ld)=%d\n",Tinv(n),n);
return 0;
}
Code: Select all
$ gcc -Wall -O3 -o limited limited.c
limited.c: In function ‘doinit’:
limited.c:51:9: warning: implicit declaration of function ‘exit’ [-Wimplicit-function-declaration]
exit(1);
^~~~
limited.c:51:9: warning: incompatible implicit declaration of built-in function ‘exit’
limited.c:51:9: note: include ‘<stdlib.h>’ or provide a declaration of ‘exit’
limited.c:8:1:
+#include <stdlib.h>
limited.c:51:9:
exit(1);
^~~~
limited.c:55:27: warning: ‘return’ with no value, in function returning non-void
if(P[i]>smax/r+1) return;
^~~~~~
limited.c:41:13: note: declared here
static void doinit(){
^~~~~~
limited.c:59:5: warning: incompatible implicit declaration of built-in function ‘exit’
exit(2);
^~~~
limited.c:59:5: note: include ‘<stdlib.h>’ or provide a declaration of ‘exit’
limited.c: In function ‘Twork’:
limited.c:132:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
$ time ./limited
T(30240)=20
real 0m0.019s
user 0m0.000s
sys 0m0.016s
If you remove the lineHeater wrote: ↑Sat Nov 09, 2019 5:41 pmSIMH is a wonderful thing. I used it's Z80 emulator and CP/M operating system when developing my Z80 emulator for the Parallax Propeller.
https://hackaday.com/2009/12/27/zilog-in-a-matchbox/
Pre-ANSI C. Oh what joy!
I'm amazed gcc compiles it on my PC without some arm twisting:
Code: Select all
$ gcc -Wall -O3 -o limited limited.c limited.c: In function ‘doinit’: limited.c:51:9: warning: implicit declaration of function ‘exit’ [-Wimplicit-function-declaration] exit(1); ^~~~ limited.c:51:9: warning: incompatible implicit declaration of built-in function ‘exit’ limited.c:51:9: note: include ‘<stdlib.h>’ or provide a declaration of ‘exit’ limited.c:8:1: +#include <stdlib.h> limited.c:51:9: exit(1); ^~~~ limited.c:55:27: warning: ‘return’ with no value, in function returning non-void if(P[i]>smax/r+1) return; ^~~~~~ limited.c:41:13: note: declared here static void doinit(){ ^~~~~~ limited.c:59:5: warning: incompatible implicit declaration of built-in function ‘exit’ exit(2); ^~~~ limited.c:59:5: note: include ‘<stdlib.h>’ or provide a declaration of ‘exit’ limited.c: In function ‘Twork’: limited.c:132:1: warning: no return statement in function returning non-void [-Wreturn-type] } $ time ./limited T(30240)=20 real 0m0.019s user 0m0.000s sys 0m0.016s
I'll take that coupon and pickup some glasses.You had some typos, most obvious was the use of 1 instead of i at line 25, if I recall correctly..
Code: Select all
' Tatami.sb
nMax = 6700000
nMaxSqrt = INT(SQR(nMax))
SPLITA STRING(nMax, "0") BY "" TO v
FUNCTION Tatami(s)
FOR i = 7 TO nMaxSqrt - 1 STEP 2
k2 = i + 3
k3 = i + i - 4
WHILE (k2 <= k3) AND ((i * k2) < nMax)
k4 = INT(nMax / i)
IF k3 < k4 THEN
k4 = k3
END IF
FOR j = k2 TO k4 STEP 2
v[i * j] += 1
NEXT
k2 += i + 1
k3 += i - 1
WEND
NEXT
FOR i = 8 TO nMaxSqrt - 1 STEP 2
k2 = i + 3
k3 = i + i - 4
WHILE (k2 <= k3) AND ((i * k2) < nMax)
k4 = INT(nMax / i)
IF k3 < k4 THEN
k4 = k3
END IF
FOR j = k2 TO k4
v[i * j] += 1
NEXT
k2 += i + 1
k3 += i - 1
WEND
NEXT
FOR i = 0 TO nMax - 1
IF v[i] = s THEN
Tatami = i
EXIT FUNCTION
END IF
NEXT
END FUNCTION
s = 100
PRINT FORMAT("The smallest room size s for which T(s) = %d is %d\n", s, Tatami(s))
Code: Select all
[email protected]:~/sbrt/examples $ time scriba Tatami_Release.sb
The smallest room size s for which T(s) = 100 is 6683040
real 0m53.394s
user 0m51.326s
sys 0m2.040s
[email protected]:~/sbrt/examples $