Liberation through Computer Literacy

[ejolson]

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.

[Heater]

John_Spikowski,

That's great. Never heard of a Terak before. I do recall a CS undergrad friend getting all excited when we spotted an LSI-11 board in some CS lab at uni, circa 1977. Not sure I ever saw one working.

At that that time the company I wound up working at a few years later had designed it's own in house 16 bit CPU. Based on AMD bit slice chips. Much the same idea, squeezing what had been a TTL logic chip design into something smaller. They were used for driving those huge round vector graphics displays used in radar systems at the time. Those displays were gorgeous.

It was a kind of parallel universe of development happening on opposite sides of the pond. Sadly on my side of the pond all such development and expertise was military and secret with no notion of making a commercial product normal people could use.

https://marconiradarhistory.pbworks.com ... Locus%2016

[John_Spikowski]

the three years estimated to run PETAMI.BAS on the PET.

I no longer feel bad about 4 hours running your QB fibo.

[John_Spikowski]

When I built my Heathkit PDP-11, Bill Gates was a few miles away fiddling in his garage. I missed the Apple exit after leaving Terak and took on a career fixing just about everything electronic in hospitals.

THEN

I found REXON which launched my software transistion.

[Heater]

Let's not rewrite history. Gates never tinkered in any garage. Except if he was fixing his bicycle as a kid. He used the computer facilities of Harvard.

[John_Spikowski]

A metaphor to establish timeline. I lived in Redmond at the time.

Bill's garage

Heater,

How does it feel to be $100 million wrong?

[ejolson]

I found REXON which launched my software transistion.

I might have a working WangDAT tape drive in storage. Otherwise, it appears I missed everything to do with Rexon.

https://en.wikipedia.org/wiki/Rexon

The T(s)=200 computation performed using the PDP-11 emulator finished with

Code: Select all

$ time ./limited
T(85765680)=200

real  1:08:56.0
user  1:08:53.9
sys         0.0

This implies it would take 10 to 11 hours to finish the computation on real PDP-11 hardware. While that's liberating to computer scientists and people like Bill Gates, who would have had access to such hardware during the golden age, it remains to be seen whether personal computers like the Commodore PET could have performed the same tatami calculation in a reasonable time.

How does the performance difference between a 6502 and a PDP-11 during the golden age compare to the performance difference between a Cortex-A72 and a Xeon server today? Are those differences due more to hardware or software?

Presently, thanks to the free software movement, the exact same software and programming languages used on the most expensive machines are also available for the least expensive single-board computers. Perhaps the critical difference between the past and now, aside from the increased affordability of hardware, is the quality of the software available to makers and hobbyists. If so, then a suitable choice of first language may be all that's needed ensure the continued health of the second age of personal computing.

[John_Spikowski]

RECAP was their Business BASIC OS. I expanded their line to a fault tolerant Novell file server with a custom SCSI driver we wrote. Early emulation of disk arrays. More of a mirroring approach.

[John_Spikowski]

It looks like around 120 is ScriptBasic's upper end.

Code: Select all

pi@RPi4B:~/sbrt/examples $ ./tatami 120
The smallest room size s for which T(s) = 120 is 19459440
pi@RPi4B:~/sbrt/examples $ time scriba Tatami_Release.sb
The smallest room size s for which T(s) = 120 is 19459440

real	2m39.167s
user	2m33.031s
sys	0m6.130s
pi@RPi4B:~/sbrt/examples $ 

It takes ScriptBasic 14.490 seconds to create/initialize a 20,000,000 element array using the SPLITA function.

This test doesn't do the SPLITA and creates the v[] array dynamically.

Code: Select all

pi@RPi4B:~/sbrt/examples $ time scriba Tatami_Release.sb 100
The smallest room size s for which T(s) = 100 is 6683040

real	1m23.532s
user	1m12.472s
sys	0m11.027s
pi@RPi4B:~/sbrt/examples $ 

This is using SPLITA to create the 6,700,000 element array initializing each element to 0. It takes 4.87 seconds for SPLITA to create v.

Code: Select all

pi@RPi4B:~/sbrt/examples $ time scriba Tatami_Release.sb 100
The smallest room size s for which T(s) = 100 is 6683040

real	0m51.170s
user	0m49.237s
sys	0m1.911s
pi@RPi4B:~/sbrt/examples $ 

[ejolson]

It looks like around 120 is ScriptBasic's upper end.

It is still not clear to me what value of n makes T(s)=n a reasonably sized problem for the Raspberry Pi and modern computing hardware in general. I copied the limited.c program from the PDP-11/70 emulator to the Ryzen 7 Pro 1700 desktop and then changed the lines

#define smax 70000000000l
#define Pnum 50000
#define fnum 20

at the beginning of the file and in main set

int n=1000;

The resulting output was

Code: Select all

$ time ./limited
T(63405342000)=1000

real    2m39.709s
user    2m39.652s
sys 0m0.003s

When I have time, I'll switch the Pi 4B to 64-bit mode and try a similar run to compare speeds. Do you think finding the least s such that T(s)=2000 would be absurd enough, or are more zeros needed?

[John_Spikowski]

Lets refine 100 first. Absurdness is creeping into the challenge again.

[John_Spikowski]

I thought I might try using an C extension module to define and maintain the v[ ] array. As it turned out calling the extension module is slower than the native arrays,

TA extension module

Code: Select all

/* Tatami Array Get / Set
UXLIBS: -lm
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../../basext.h"
#include "cbasic.h"

DIM AS unsigned char v[100000000];

/****************************
 Extension Module Functions
****************************/

besVERSION_NEGOTIATE
  RETURN_FUNCTION((int)INTERFACE_VERSION);
besEND

besSUB_START
  DIM AS long PTR p;
  besMODULEPOINTER = besALLOC(sizeof(long));
  IF (besMODULEPOINTER EQ NULL) THEN_DO RETURN_FUNCTION(0);
  p = (long PTR)besMODULEPOINTER;
  RETURN_FUNCTION(0);
besEND

besSUB_FINISH
  DIM AS long PTR p;
  p = (long PTR)besMODULEPOINTER;
  IF (p EQ NULL) THEN_DO RETURN_FUNCTION(0);
  RETURN_FUNCTION(0);
besEND


/************************
 Tatami array functions
************************/

besFUNCTION(get_v)
  DIM AS long idx;
  DIM AS long value;
  besARGUMENTS("i")
    AT idx
  besARGEND
  value = v[idx];
  besRETURN_LONG(value);
besEND

besFUNCTION(set_v)
  DIM AS long idx;
  DIM AS long value;
  besARGUMENTS("ii")
    AT idx, AT value
  besARGEND
  v[idx] = value;
  besRETURNVALUE = NULL;
besEND

This test program assigns the FOR value to each element of the index. The problem using this with the Tatami challenge is to set an array element value you have to read it first which doubles the time needed,

Code: Select all

DECLARE SUB get_v ALIAS "get_v" LIB "ta"
DECLARE SUB set_v ALIAS "set_v" LIB "ta"

FOR x = 0  To 6700000
  set_v(x,x)
NEXT

Output

Code: Select all

pi@RPi4B:~/sbrt/examples $ time scriba t_ext.sb

real	0m17.291s
user	0m17.246s
sys	0m0.042s
pi@RPi4B:~/sbrt/examples $ 

Here is the above but using a native ScriptBasic array.

Code: Select all

SPLITA STRING(6700001, "0") BY "" TO v
FOR x = 0  To 6700000
  v[x] = x
NEXT


pi@RPi4B:~/sbrt/examples $ time scriba t_na.sb

real	0m15.558s
user	0m13.098s
sys	0m2.453s
pi@RPi4B:~/sbrt/examples $ 

[John_Spikowski]

I added a new function to the extension module called add_v which reduces the v bumps to one call instead of two.

Here is 100. The only silver lining is I will be able to do 200 but no prizes expected.

Code: Select all

pi@RPi4B:~/sbrt/examples $ time scriba Tatami_ext.sb 100
The smallest room size s for which T(s) = 100 is 6683040

real	12m10.151s
user	12m9.426s
sys	0m0.432s
pi@RPi4B:~/sbrt/examples $ 

I'll post the 200 results when they come in.

Tatami_ext.sb

Code: Select all

' Tatami.sb

DECLARE SUB get_v ALIAS "get_v" LIB "ta"
DECLARE SUB set_v ALIAS "set_v" LIB "ta"
DECLARE SUB add_v ALIAS "add_v" LIB "ta"

nMax = 100000000

nMaxSqrt = INT(SQR(nMax))

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
        add_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
          add_v(i * j, 1)
        NEXT
        k2 += i + 1
        k3 += i - 1
    WEND
  NEXT
  FOR i = 0 TO nMax - 1
    IF get_v(i) = s THEN
      Tatami = i
      EXIT FUNCTION
    END IF
  NEXT
END FUNCTION

s = VAL(COMMAND())
PRINT FORMAT("The smallest room size s for which T(s) = %d is %d\n", s, Tatami(s))

interface.c (TA extension module using my C BASIC preprocessor include)

Code: Select all

/* Tatami Array Get / Set / Add
UXLIBS: -lm
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../../basext.h"
#include "cbasic.h"

DIM AS unsigned char v[100000000];

/****************************
 Extension Module Functions
****************************/

besVERSION_NEGOTIATE
  RETURN_FUNCTION((int)INTERFACE_VERSION);
besEND

besSUB_START
  DIM AS long PTR p;
  besMODULEPOINTER = besALLOC(sizeof(long));
  IF (besMODULEPOINTER EQ NULL) THEN_DO RETURN_FUNCTION(0);
  p = (long PTR)besMODULEPOINTER;
  RETURN_FUNCTION(0);
besEND

besSUB_FINISH
  DIM AS long PTR p;
  p = (long PTR)besMODULEPOINTER;
  IF (p EQ NULL) THEN_DO RETURN_FUNCTION(0);
  RETURN_FUNCTION(0);
besEND


/************************
 Tatami array functions
************************/

besFUNCTION(get_v)
  DIM AS long idx;
  DIM AS long value;
  besARGUMENTS("i")
    AT idx
  besARGEND
  value = v[idx];
  besRETURN_LONG(value);
besEND

besFUNCTION(set_v)
  DIM AS long idx;
  DIM AS long value;
  besARGUMENTS("ii")
    AT idx, AT value
  besARGEND
  v[idx] = value;
  besRETURNVALUE = NULL;
besEND

besFUNCTION(add_v)
  DIM AS long idx;
  DIM AS long value;
  besARGUMENTS("ii")
    AT idx, AT value
  besARGEND
  v[idx] += value;
  besRETURNVALUE = NULL;
besEND

Wow!

I was expecting it to take much longer at 200.

Code: Select all

pi@RPi4B:~/sbrt/examples $ time scriba Tatami_ext.sb 200
The smallest room size s for which T(s) = 200 is 85765680

real	17m7.563s
user	17m6.692s
sys	0m0.432s
pi@RPi4B:~/sbrt/examples $ 

Just a reminder that ScriptBasic completed 100 in 53 seconds using its native array feature.

[ejolson]

The linkage to C seems pretty efficient. Congratulations on solving T(s)=200 with ScriptBasic. It's amazing what can be done to get around limitations. I'm currently looking at Steve Wozniak's Sweet16 virtual machine to see whether that could help the PET find tatami-free rectangles. In a way similar to mixing C with Basic, it's interesting how one can efficiently intermingle Sweet16 opcodes with regular 6502 assembler.

Do you think finding the least s such that T(s)=2000 would be absurd enough, or are more zeros needed?

Changing the lines

#define smax 1500000000000l
#define Pnum 150000
#define fnum 20

at the beginning of limited.c and in main writing

int n=2000;

resulted in

Code: Select all

T(1459731873600)=2000
2621.49user 0.00system 43:42.40elapsed 99%CPU (0avgtext+0avgdata 3160maxresident)k
0inputs+8outputs (0major+370minor)pagefaults 0swaps

on a Ryzen 7 Pro 1700 desktop computer. Note that the maximum resident size is still under 4GB so the calculation should be within the reach of the 4GB version of the Pi 4B. Unfortunately, I bought the 2GB model. Interestingly, the answer is found within a couple minutes and the rest of the time is spent verifying s is actually the smallest value such that T(s)=2000.

Recall that the original algorithm described by tatami.c stores all values of T(s) up to the some limit on s and then scans the array to find the smallest s such that T(s)=n. While storing an array for all values up to s=1459731873600 would take 1.4TB of RAM, it is also possible to break that array up into slices that only store values of T(s) for s from m*G to (m+1)*G where G=1073741824 and then loop for m from 0 to 1399. I'm not sure whether that would be faster than the present calculation; however, such a technique could easily lead to a parallel computation that simultaneously uses 1400 Raspberry Pi computers, one for each value of m.

[John_Spikowski]

Are we ready to start plotting these Tatami rooms before the challenge grows to cover the surface of the earth?

[John_Spikowski]

Strange no one has submitted a Python example yet.

[ejolson]

Strange no one has submitted a Python example yet.

I think the difficulty might be in understanding what needs to be done to answer the challenge question and exactly why or whether it is interesting.

Finding T(s) is about factoring s into i by j rectangles such that s=i*j and then applying some condition to determine whether the floor of such a rectangle can be covered by tatami carpets or not. I asked the lead developer of FidoBasic why that's interesting. With a growl the dog developer said, if you can efficiently solve the tatami carpet problem for large values of s, expect an interesting knock on the door from the RSA.

From what I understand, the RSA encryption algorithm (used to protect credit-card transactions over the Internet) is based on the fact that it is easy to multiply numbers together to make a large number but rather difficult to factor a large one into its constituent primes. Could it be that the tatami problem is a thinly-disguised way to research cryptography? Is it possible people are not posting Python code because they don't want a knock on the door? On the other hand, maybe not.

[John_Spikowski]

Wow!

Blind sided with that response. I guess I won't be searching online for grass Tatami rectangles.

[ejolson]

Wow!

Blind sided with that response. I guess I won't be searching online for grass Tatami rectangles.

Personally I'd love to have a chance to talk with either Ron Rivest, Adi Shamir or Leonard Adleman; however, I don't know what they'd do with tatami carpets other than maybe some yoga poses.

https://en.wikipedia.org/wiki/RSA_(cryptosystem)

[John_Spikowski]

I like your idea about doing this in threads. Can you post an example of parallel processing?

It's amazing what can be done to get around limitations. 

Practically speaking, there are no limitations with ScriptBasic.

[Heater]

John_Spikowski,

Practically speaking, there are no limitations with ScriptBasic.

Dang. Now I have to clean a mouthful of my morning coffee out of my keyboard.

[John_Spikowski]

Dang. Now I have to clean a mouthful of my morning coffee out of my keyboard.

That's why we can't take you anywhere.

Let me know if you find something better that fits in a 150 KB zip.

[Heater]

https://en.wikipedia.org/wiki/Tiny_C_Compiler

[John_Spikowski]

If I need a compiler I'll use gcc.

My 150 KB request was for a high level language like an interpreter.

[ejolson]

Dang. Now I have to clean a mouthful of my morning coffee out of my keyboard.

That's why we can't take you anywhere.

Let me know if you find something better that fits in a 150 KB zip.

The ROM for the Commodore PET took 16K and included a Basic interpreter, editor, a mathematics library and various input-output routines. Version 4 took another 4K and included better memory management along with a simple disk operating system.

I think the claim there are no practical limitations with ScriptBasic refers to the idea that human ingenuity can always find a work around.

This afternoon I saw Fido on top of the dog house wearing a blue cape. When asked what was going on, the developer replied, I'm testing the capabilities of the super pet. Worried, I quickly explained, that the SuperPET is an auxiliary 6809 processor board designed to work around some limitations in the native 6502. From a literacy point of view, the ability to run Waterloo Basic, Fortran and Pascal make the PET much more liberating.

Although a free software workaround is preferable to expensive hardware, any workaround presents the user with a learning curve interrupted by road blocks and the occasional goose crossing. However, at the mention of goose, Fido jumped and immediately plummeted to the ground. Fortunately, nothing was hurt that couldn't be fixed by a quick trip to Salisbury Super Pet to buy dog treats.