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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 1:26 am

I'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$ 

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 2:14 am

John_Spikowski wrote:
Sat Nov 09, 2019 1:26 am
I'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$ 
If you use integer division or something like INT(nMax/i) does it work?

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 2:34 am

No help. I tried that early on.

You only need scriba to run this.

./scriba Tatami_Final.sb

Compiled for RPi 3-4. No Zero support.
Attachments
scriba.zip
(150.42 KiB) Downloaded 1 time
Last edited by John_Spikowski on Sat Nov 09, 2019 2:51 am, edited 1 time in total.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 2:45 am

John_Spikowski wrote:
Sat Nov 09, 2019 2:34 am
No help. I tried that early on.

You only need scriba to run this.
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.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 2:55 am

The C version works.

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 $ 
Can you make that 200? Give me a second.
Last edited by John_Spikowski on Sat Nov 09, 2019 4:57 am, edited 3 times in total.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 3:52 am

ejolson wrote:
Thu Nov 07, 2019 5:53 pm
At anyrate, the run just finished with the correct result, so that rules out any obvious bugs.

Image

A computation to find the smallest s such that T(s)=100 is now in progress.
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
That's slightly more than a day of work.

If cbmbasic is really 1000 times faster than the original PET, that means it would have taken 3 years to perform the same calculation during the golden age of personal computing. Moreover, assuming the simple algorithm used in PETAMI.BAS scales as O(s^1.5), this further implies that the T(s)=200 computation would take

(85765680/6683040)^1.5=50

times longer. In other words, 50 days using cbmbasic or about 150 years using the original PET hardware. I suspect a different algorithm is needed.

When I went to report my findings to the testing and quality assurance department, the former developer of FidoBasic looked up and barked, 150 years can pass very quickly if you have a time machine. I confirmed that I did, but even then the calculation would take 50 days. There was silence, so I added, I think a better program is needed.

Some more time passed and this time the silence was broken by the sound of clicking, dragging and dropping. Fido had gone back to work and was trying to embed graphs made of ASCII art into the bubble comment boxes of Scratch.
Last edited by ejolson on Sat Nov 09, 2019 5:47 am, edited 1 time in total.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 4:06 am

@ejolson's VB converted code.

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"
Output

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 $ 
I'm assuming this is the time we will see if only the results were correct.

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 $ 

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 5:08 am

It seems that Fido was able to borrow the Tardis one more time. This time the tour included 5 of the nearest 10 interesting events in four-dimensional space time to the creation of the Unix operating system. Historic Unix R7 was running on a newly installed PDP-11/70. Fortunately, I had suitable level-shifters so I could connect my Raspberry Pi to the DZ11 serial controller. After a little editing I obtained the output

Code: Select all

$ time ./recurse
T(30240)=20

real     3:45.0
user     3:43.9
sys         0.1
in 3 minutes 45 seconds for the program

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;
}
I did not compute T(s)=100 out of consideration for others. Anyway, thought I, it will be cheaper to run the longer calculation when I get home using hardware emulation. Note that the exact PDP-11/70 I used was named Miss Piggy and is located at the Living Computers Museum in Seattle.

Image
Last edited by ejolson on Sat Nov 09, 2019 4:57 pm, edited 4 times in total.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 5:15 am

The only thing that looks familiar is the DEC Writer. I bought one with my Heathkit PDP-11 I built.

So you live in Seattle?

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 5:34 am

John_Spikowski wrote:
Sat Nov 09, 2019 5:15 am
The only thing that looks familiar is the DEC Writer. I bought one with my Heathkit PDP-11 I built.
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?

While it is fun to emulate a PET using the Pi, running software and operating systems designed for mainframe and minicomputers feels very liberating.
John_Spikowski wrote:
Sat Nov 09, 2019 5:15 am
So you live in Seattle?
No. I ran my code on Miss Piggy remotely by logging in over the Internet.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 6:10 am

That's awesome. The last time I saw a DECwriter it was attached to a Data General Nova deep in an underground bunker. It was printing out any alarms that were generated by an entire cities traffic lights. They only took it out of service about 8 years ago when the washing machine sized hard drive started making noises like a concrete mixer and they thought it was perhaps time for an upgrade.
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 6:11 am

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?
Wish I kept it but it was lost under the no touch in two years it's gone rule. 8-)

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 6:32 am

ejolson wrote:
Sat Nov 09, 2019 5:08 am
Historic Unix R7 was running on a newly installed PDP-11/70.
Maybe I should start up Soviet built PDP-11 compatible UKNC computer running RT-11 operating system and try running the tatami code....

I also have access to most of the Soviet built highly modified ZX-Spectrum clones. Those could also be used to run tatami code.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 7:15 am

How about THIS as a prize?

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 7:27 am

Has 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.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 1:39 pm

John_Spikowski wrote:
Sat Nov 09, 2019 7:27 am
Has 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.
Here you are John , thanks for letting me keep my scalp! ;)

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))

User avatar
jcyr
Posts: 427
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 2:13 pm

ejolson wrote:
Sat Nov 09, 2019 5:08 am
Historic Unix R7 was running on a newly installed PDP-11/70.
Ah yes, the PDP-11. It was the PDP-11 that got me hooked. More specifically the GT40. It had a built-in vector graphics co-processor and a kick ass lunar lander simulation. It has gotten rather boring since, with only 2 architectures (ARM & X86) left competing for dominance.
It's um...uh...well it's kinda like...and it's got a bit of...

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 4:27 pm

jcyr,
It has gotten rather boring since, with only 2 architectures (ARM & X86) left competing for dominance.
Don't get bored with computer architectures.. Get into RISC V
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 4:28 pm

ejolson wrote:
Sat Nov 09, 2019 5:08 am
After a little editing I obtained the output

Code: Select all

$ time ./recurse
T(30240)=20

real     3:45.0
user     3:43.9
sys         0.1
in 3 minutes 45 seconds
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.

Conversation turned to remodeling the dog house by covering the floor with tatami carpets. In passing the lead developer of FidoBasic remarked, you know, it is not possible to have n tatami-free rectangles of size i*j with i<=j unless the area s has at least 2n different divisors. Using this observation I created the program limited.c which on the PDP-11/70 resulted in

Code: Select all

$ time ./limited
T(30240)=20

real     1:52.0
user     1:51.5
sys         0.1
That's a two-fold improvement in performance over the previous run. It seems likely that T(s)=100 if not T(s)=200 is possible using 50-year-old technology.

While the PDP-11/70 was never a personal computer, as has been mentioned, the LSI-11/03 was sold by Heathkit for exactly that purpose. At the same time, liberation of all people through computer literacy is only possible when all people can afford a computer. Fortunately, it is possible to emulate most minicomputers using a Raspberry Pi.

https://www.raspberrypi.org/forums/view ... 9&t=163320

For reference the improved code is

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;
}

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 5:41 pm

SIMH 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
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 6:22 pm

Heater wrote:
Sat Nov 09, 2019 5:41 pm
SIMH 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
If you remove the line

#define void int

and include stdlib.h then most of those warnings should go away. I'm currently running T(s)=100 using SIMH.

I wonder how large n should be to make a suitably absurd but possible challenge for today's computing hardware. Since this challenge now has a generous benefactor providing tatami carpets to the winners, it would appear we could increase the difficultly a bit.

Along different lines I hope our generous forum moderator made it home last night in spite of reading this thread while driving and all the farm machinery on the road. Do you think any of those tractors were hauling raspberries?

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 6:25 pm

You had some typos, most obvious was the use of 1 instead of i at line 25, if I recall correctly..
I'll take that coupon and pickup some glasses.

Thanks for your time and help!

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 6:39 pm

One of my early jobs after building the Heathkit PDP-11 was working for Terak as a field service engineer. Mostly servicing universities and higher learning facilities.

I also owned S/N 6 of the IBM XT. I was running 8 Wyse terminals using Througbred Business BASIC OS.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 7:42 pm

Tatami ScriptBasic

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))
Output

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 $ 

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 8:28 pm

John_Spikowski wrote:
Sat Nov 09, 2019 6:39 pm
One of my early jobs after building the Heathkit PDP-11 was working for Terak as a field service engineer. Mostly servicing universities and higher learning facilities.
I wonder whether the golden age of personal computing would have lasted longer if the UCSD p-system had been made open source. Instead, it was expensive and never evolved to include a programmable shell or hierarchical filesystem. On the other hand, as demonstrated by the modern mouse interface, people don't want a current working directory nor even the ability to automate repetitive tasks. The reason seems to be that it's much easier to perform manual labor with a shovel or mouse rather than learning how to read and write computer programs. Unfortunately, without such literacy how can there be any liberation?

I chose to emulate the 44-year-old PDP-11/70 using a 19-year-old AMD Athlon Thunderbird that was fortunately not being emulated by the Raspberry Pi. The results were

Code: Select all

$ time ./limited
T(30240)=20

real       12.0
user       11.9
sys         0.0
which indicate the emulated PDP-11 is almost 10 times faster than the original hardware. Making the changes

#define smax 10000000l
#define Pnum 600

at the beginning of limited.c and then in main changing

int n=100;

resulted in the output

Code: Select all

$ time ./limited
T(6683040)=100

real    14:59.0
user    14:53.2
sys         0.0
This suggests T(s)=100 would finish in less than three hours on a real PDP-11. Note that three hours is much more liberating than the three years estimated to run PETAMI.BAS on the PET. For reference, the Raspberry Pi 4B running a natively compiled version of limited.c completes the same calculation in 0.507 seconds. A computation for T(s)=200 is now in progress.
Last edited by ejolson on Sat Nov 09, 2019 9:11 pm, edited 1 time in total.

Return to “General programming discussion”