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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 9:07 pm

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

Image
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 9:15 pm

the three years estimated to run PETAMI.BAS on the PET.
I no longer feel bad about 4 hours running your QB fibo.

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 10:43 pm

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
Posts: 13648
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 10:48 pm

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

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

Re: Liberation through Computer Literacy

Sat Nov 09, 2019 10:52 pm

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
Posts: 3708
Joined: Tue Mar 18, 2014 11:47 am

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 2:12 am

John_Spikowski wrote:
Sat Nov 09, 2019 10:43 pm
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.
Last edited by ejolson on Sun Nov 10, 2019 2:53 am, edited 11 times in total.

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 2:40 am

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.

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 4:58 am

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
Posts: 3708
Joined: Tue Mar 18, 2014 11:47 am

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 7:37 am

John_Spikowski wrote:
Sun Nov 10, 2019 4:58 am
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?

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 9:02 am

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

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 9:45 am

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, :cry:

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 $ 

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 10:31 am

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.
Last edited by John_Spikowski on Sun Nov 10, 2019 11:45 pm, edited 5 times in total.

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 5:47 pm

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.
ejolson wrote:
Sun Nov 10, 2019 7:37 am
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.

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 7:23 pm

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

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

Re: Liberation through Computer Literacy

Sun Nov 10, 2019 11:39 pm

Strange no one has submitted a Python example yet.

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 12:09 am

John_Spikowski wrote:
Sun Nov 10, 2019 11:39 pm
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.

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 12:21 am

Wow!

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

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 12:28 am

John_Spikowski wrote:
Mon Nov 11, 2019 12:21 am
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)

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 1:37 am

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
Posts: 13648
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 3:44 am

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

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 4:00 am

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
Posts: 13648
Joined: Tue Jul 17, 2012 3:02 pm

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 7:02 am

Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 7:08 am

If I need a compiler I'll use gcc.

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

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 7:23 am

John_Spikowski wrote:
Mon Nov 11, 2019 4:00 am
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.

Image
Last edited by ejolson on Mon Nov 11, 2019 8:07 am, edited 12 times in total.

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

Re: Liberation through Computer Literacy

Mon Nov 11, 2019 7:30 am

I think the idea that there are no practical limitations with ScriptBasic refers to idea that human ingenuity can always find a work around.
Not only can you expand ScriptBasic with C functions, you can create ScriptBasic commands. Actually I prefer running ScriptBasic threaded as a shared object.

Return to “General programming discussion”