Liberation through Computer Literacy

[John_Spikowski]

Does tiling the floors of rectangular rooms with tatami carpets help in any way?

Puzzling question.

[Heater]

ejolson,

Before placing blame for the ensuing digital dark ages on Basic itself...

We can pin point the start of the Digital Dark Ages to February 3rd, 1976.

That is the date that Bill Gates posted his infamous "Letter to Hobbyists" in which he outlined his plans for making all the software that users of the emerging personal computers might use closed source, proprietary, protected by copyright and for profit.
https://commons.wikimedia.org/wiki/File ... byists.jpg

The idea being that we, software gurus, write the code while you, ignorant peasants, pay us.

A brilliant plan. Morally bankrupt but brilliant.

All of a sudden the BASIC that was created as means to bring computer literacy and liberation to all was subverted into a tool for one man to make money. And that was only the beginning.

Nobody saw this plan so clearly at the time as Richard Stallman. Hence GCC and hence Linux... as you know.

Maybe the desire of many to strike it rich by selling proprietary software was the real reason behind the end of the golden age. Linus could not have written an operating system before the last hacker at MIT created gcc.

Yeah, that.

Although the foundations for the second age of personal computing appear quite solid...

I'm not so optimistic:

1) Very few lust for personal computers anymore. They do all they need with appliances that use services in the "cloud".

2) Today it's not the software that matters. It can all be Free and Open Source. Where we are imprisoned is in that it's the data that matters. The likes of Google, Facebook, Microsoft, etc don't care if we have the same source code as they are using. They have all our data. They know everything about us.

Knowledge is power...

3) Will any of those kids learning software skills with the Pi today save their generation from software enslavement in the future?

[Heater]

John_Spikowski,

Strictly speaking there are no associative arrays in ScriptBasic...

Who are you quoting there?

Now you have to explain something because the message I always got before is that ScriptBasic arrays are not any kind of normal array in linearly addressable memory. But rather associative arrays and hence the appalling performance when used for regular array operations.

What actually is a ScriptBasic array?

[jahboater]

John_Spikowski,

Strictly speaking there are no associative arrays in ScriptBasic...

Who are you quoting there?

Now you have to explain something because the message I always got before is that ScriptBasic arrays are not any kind of normal array in linearly addressable memory. But rather associative arrays and hence the appalling performance when used for regular array operations.

What actually is a ScriptBasic array?

Didn't someone say earlier that they are linked lists

[John_Spikowski]

Who are you quoting there?

ScriptBasic User Guide.

[Heater]

So what is it?

Scanning a linked list to find the value that has a key "idx" where "idx" is what we might normally think is an array index: someArray[idx].

Or some kind of hash table, where "idx" is used to create a hash which quickly finds the element we want? Which I doubt as it is so slow.

Or something else?

Whatever it is, linked list, hash table, binary tree, etc, it can be seen as an associative key-value store rather than a regular array.

Hmm actually, thinking about that "associative array" thing. Literally it means ScriptBasic doe not have arrays as the linearly addresses areas of memory we know and love. That associate an index directly to a memory address. Rather it has some other data structure as an associative, key - value, store. That just looks like an array syntactically.

Which is what Javascript does as it happens. Except JS will optimize things like someArray[idx] to actual fast linear arrays when "idx" is always an integer.

[John_Spikowski]

If I can get the HASH extension module to work, I wonder if I can use it instead of ScriptBasic Arrays? Would it be faster than the TA extension module I wrote?

[John_Spikowski]

I added do_v to the TA extension module to handle the inner FOR/NEXT that updated the v array.

interface.c

Code: Select all

besFUNCTION(do_v)
  DIM AS long start;
  DIM AS long end;
  DIM AS long value;
  DIM AS long idx;
  besARGUMENTS("iii")
    AT start, AT end, AT value
  besARGEND
  DEF_FOR (idx = start TO idx <= end STEP INCR idx + 2)
  BEGIN_FOR
    v[value * idx] += 1;
  NEXT
  besRETURNVALUE = NULL;
besEND   

tatamix.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"
DECLARE SUB do_v  ALIAS "do_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
      do_v(k2, k4, i)
      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
        do_v(k2, k4, i)        
        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))

Output (Laptop)

Code: Select all

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

real	1m50.241s
user	1m50.176s
sys	0m0.060s
ubuntu@ubuntu:~/sbrt/examples$ 

[ejolson]

I added do_v to the TA extension module to handle the inner FOR/NEXT that updated the v array.

interface.c

Code: Select all

besFUNCTION(do_v)
  DIM AS long start;
  DIM AS long end;
  DIM AS long value;
  DIM AS long idx;
  besARGUMENTS("iii")
    AT start, AT end, AT value
  besARGEND
  DEF_FOR (idx = start TO idx <= end STEP INCR idx + 2)
  BEGIN_FOR
    v[value * idx] += 1;
  NEXT
  besRETURNVALUE = NULL;
besEND   

tatamix.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"
DECLARE SUB do_v  ALIAS "do_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
      do_v(k2, k4, i)
      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
        do_v(k2, k4, i)        
        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))

Output (Laptop)

Code: Select all

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

real	1m50.241s
user	1m50.176s
sys	0m0.060s
ubuntu@ubuntu:~/sbrt/examples$ 

Am I right that your code now runs more than twice as fast?

[John_Spikowski]

I added find_s to the TA extension module which is the find s FOR/NEXT in the v array.

interface.c

Code: Select all

besFUNCTION(find_s)
  DIM AS long s;
  DIM AS long idx;
  besARGUMENTS("i")
    AT s
  besARGEND
  DEF_FOR (idx = 0 TO idx <= 99999999 STEP INCR idx)
  BEGIN_FOR
    IF (v[idx] == s) THEN_DO besRETURN_LONG(idx);
  NEXT
besEND  

besFUNCTION(do_v)
  DIM AS long start;
  DIM AS long end;
  DIM AS long value;
  DIM AS long idx;
  besARGUMENTS("iii")
    AT start, AT end, AT value
  besARGEND
  DEF_FOR (idx = start TO idx <= end STEP INCR idx + 2)
  BEGIN_FOR
    v[value * idx] += 1;
  NEXT
  besRETURNVALUE = NULL;
besEND   

tatamix.sb

Code: Select all

' Tatamix.sb

DECLARE SUB do_v    ALIAS "do_v"    LIB "ta"
DECLARE SUB find_s  ALIAS "find_s"  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
      do_v(k2, k4, i)
      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
      do_v(k2, k4, i)        
      k2 += i + 1
      k3 += i - 1
    WEND
  NEXT
  Tatami = find_s(s)
END FUNCTION

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

Output (laptop)

Code: Select all

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

real	0m5.894s
user	0m5.838s
sys	0m0.056s
ubuntu@ubuntu:~/sbrt/examples$ 

Output (RPi 4B 4GB)

Code: Select all

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

real	0m26.649s
user	0m26.327s
sys	0m0.311s
pi@RPi4B:~/sbrt/examples $ 

[ejolson]

We can pin point the start of the Digital Dark Ages to February 3rd, 1976.

Just think how the history of personal computing would have been changed if Microsoft had really delivered a version of APL for those early 8-bit processors!

I'm not sure Bill Gates was the one who convinced the judges of the US justice system that computer software was a literary art which could be copyrighted as opposed to a mathematical algorithm which couldn't. At the time there were many of either persuasion. Given how the division of government powers among three branches is supposed to work, as I see it, the difficulty was the legislators did not perform a proper game-theoretic analysis to determine whether the resulting Nash equilibrium would lead to computer literacy and economic growth or the opposite.

Since the laws which define intellectual property are made up by people in the first place, then it only makes sense for those laws to be made up in a way that benefits people.

As I typed the above sentence, the dog developer--looking a bit sick from eating so many dog treats--suddenly barked, don't forget IBM. The friends of those same judges had just won an antitrust lawsuit which declared it was an unfair practice to develop and provide free software with IBM computers. My friend Bill was a lucky businessman who likes dogs, not an evil force that caused the collapse of the golden age. Before I could ask how Fido became friends with the billionaire, the dog developer turned over and went to sleep snoring loudly.

[John_Spikowski]

Maybe a good group project would be to expand on C BASIC to fill out the syntax?

Here is the interface.c TA extension module in native C.

Code: Select all

unsigned char v[100000000];

int versmodu(int Version, char *pszVariation, void **ppModuleInternal){
  return((int)11);
return 0;}

 int bootmodu(pSupportTable pSt, void **ppModuleInternal, pFixSizeMemoryObject pParameters, pFixSizeMemoryObject *pReturnValue){ pExecuteObject pEo=
((void *)0);
  long * p;
  (*ppModuleInternal) = (pSt->Alloc((sizeof(long)),pSt->pEo->pMemorySegment));
  if ((*ppModuleInternal) == ((void *)0)
     ) return(0);
  p = (long *)(*ppModuleInternal);
  return(0);
return 0;}

 int finimodu(pSupportTable pSt, void **ppModuleInternal, pFixSizeMemoryObject pParameters, pFixSizeMemoryObject *pReturnValue){ pExecuteObject pEo=
((void *)0);
  long * p;
  p = (long *)(*ppModuleInternal);
  if (p == ((void *)0)
    ) return(0);
  return(0);
return 0;}

 int do_v(pSupportTable pSt, void **ppModuleInternal, pFixSizeMemoryObject pParameters, pFixSizeMemoryObject *pReturnValue){ pExecuteObject pEo=
((void *)0);
  long start;
  long end;
  long value;
  long idx;
  int iError; iError = pSt->basext_GetArgsF(pSt,pParameters,("iii"),
    & start, & end, & value
  ); if( iError )return iError;
  for (idx = start ; idx <= end ; ++ idx + 2)
  {
    v[value * idx] += 1;
  }
  (*pReturnValue) = ((void *)0);
return 0;}

 int find_s(pSupportTable pSt, void **ppModuleInternal, pFixSizeMemoryObject pParameters, pFixSizeMemoryObject *pReturnValue){ pExecuteObject pEo=
((void *)0);
  long s;
  long idx;
  int iError; iError = pSt->basext_GetArgsF(pSt,pParameters,("i"),
    & s
  ); if( iError )return iError;
  for (idx = 0 ; idx <= 99999999 ; ++ idx)
  {
    if (v[idx] == s) {
     do{(*pReturnValue) = (pSt->NewMortalLong(pSt->pEo->pMo,pSt->pEo->pGlobalMortalList)); if( (*pReturnValue) == 
((void *)0))return 1; (((*pReturnValue))->Value.lValue) = (idx); return 0; }while(0);;
     break;
    }
  }
return 0;}

[jalih]

I added find_s to the TA extension module...

You should update your tatami code to jcyr's fixed version. Your current version got buffer overrun by one when writing to array...

Change all:

Code: Select all

k4 = INT(nMAX/i)

To:

Code: Select all

k4 = INT((nMAX-1)/i)

[John_Spikowski]

Nice catch.

Thanks!

[John_Spikowski]

ScriptBasic Tatami Update

interface.c

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(do_v)
  DIM AS long start;
  DIM AS long end;
  DIM AS long value;
  DIM AS long idx;
  besARGUMENTS("iii")
    AT start, AT end, AT value
  besARGEND
  DEF_FOR (idx = start TO idx <= end STEP INCR idx + 2)
  BEGIN_FOR
    v[value * idx] += 1;
  NEXT
  besRETURNVALUE = NULL;
besEND 

besFUNCTION(find_s)
  DIM AS long s;
  DIM AS long idx;
  besARGUMENTS("i")
    AT s
  besARGEND
  DEF_FOR (idx = 0 TO idx <= 99999999 STEP INCR idx)
  BEGIN_FOR
    IF (v[idx] == s) THEN
    	besRETURN_LONG(idx);
    	EXIT_FOR
    END_IF
  NEXT
besEND  

tatamix.sb

Code: Select all

' Tatamix.sb

DECLARE SUB do_v    ALIAS "do_v"    LIB "ta"
DECLARE SUB find_s  ALIAS "find_s"  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 -1) / i)
      IF k3 < k4 THEN
        k4 = k3
      END IF
      do_v(k2, k4, i)
      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 -1) / i)
      IF k3 < k4 THEN
        k4 = k3
      END IF
      do_v(k2, k4, i)
      k2 += i + 1
      k3 += i - 1
    WEND
  NEXT
  Tatami = find_s(s)
END FUNCTION

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

Output (Lenovo Laptop)

Code: Select all

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

real	0m5.931s
user	0m5.894s
sys	0m0.037s
ubuntu@ubuntu:~/sbrt/examples$ 

Output (RPi 3B 4GB)

Code: Select all

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

real	0m26.700s
user	0m26.373s
sys	0m0.321s
pi@RPi4B:~/sbrt/examples $ 

[John_Spikowski]

@jcyr's latest C code with his best optimization flags on my RPI 4B 4GB.

Code: Select all

pi@RPi4B:~/sbrt/examples $ gcc -O3 -march=native -mtune=cortex-a53 -o tatami tatami.c
pi@RPi4B:~/sbrt/examples $ time ./tatami 200
T(85765680) = 200

real	0m10.455s
user	0m10.110s
sys	0m0.340s
pi@RPi4B:~/sbrt/examples $ 

[ejolson]

They do all they need with appliances that use services in the "cloud".

In my opinion the cloud is nothing new. Cloud services such as CompuServe were very popular at the dawn of the golden age of personal computing and widely deployed by businesses outsourcing their data centers. As with present timesharing services--Amazon, Azure and the IBM Cloud--using someone else's computer has advantages as well as drawbacks.

With a modern decrease in the reliability of the electrical grid along with the greater role played by outward facing network resources for non-IT-related businesses, using someone else's computer could be a good idea. An alternative would be to locate your own machines in someone else's datacenter with guarantees on power, AC and network availability. For a technology-based company with significant inward-facing computational needs and expertise, colocation and cloud are less likely good ideas. For a person, canine or feline who values individual liberty and freedom, the only sensible choice is a fully-owned personal computer. These days such a computer can be obtained at the price of a dinner for two, if not for free attached to a magazine cover.

There are notable computer literacy projects such as Scratch3, NCLab and others that leverage the cloud. I'm not affiliated with any such project but can see the potential. Unfortunately, cloud resources are not available to all schools and individuals. Moreover, there are always terms and conditions when sharing time on someone else's computer that deny a person the freedom to run any algorithm that person is able to think up. For example, if computing T(s) for large values of s really were cryptographic research, then it would not be possible to solve the tatami challenge using cloud resources hosted in certain countries.

Whether hive-mind efficiency is more important than liberation through computer literacy is a topic that may be interesting to discuss, or not.

[John_Spikowski]

Cloud services such as CompuServe were very popular at the dawn of the golden age of personal computing and widely deployed by businesses outsourcing their data centers.

My online life started with Compuserve using a 1200 baud modem and a Osborne 'portable' computer. My bad eyesight began on that 4 inch screen.

[Heater]

ejolson,

In my opinion the cloud is nothing new.

There is nothing new under the sun. Looked at that way I can claim to have used "cloud" computing in 1972. At our tech college where we communed with some mainframe in a different city using a teletype connected via acoustic coupler and modem. The glorious old times when we were introduced to programming with BASIC. Still, we had local storage on paper tape and luckily they insisted we become fluent in assembler as well.

What I was getting at with my comment is that the overwhelming majority of computer users don't use their devices as computers. They use them as appliances to watch video, listen to music, chat to each other, play ganes, etc, etc. There is no computer literacy going on there.

With a modern decrease in the reliability of the electrical grid...

Only in third world countries that can't afford or can't organize themselves well enough to keep their infrastructure in good shape.

But yes, it's neat to be able to have your data and services spread over different data centers, with different companies, in different countries. The ultimate back up! Where would I be without github, bitbucket and the like?

On the down side, every week we read of some major data leak from some major service. Millions of records or personal data just hanging out on the net for anyone to grab. Be it some government service, medical records, genetic data, etc, etc. We can assume that once the data hits the cloud they might as well have posted it a public github repo for all the security there is. I find it horrifying.

On the other down side, pretty much any data about you that any organization gathers is traded among all kind of shadowy figures we know nothing about. Even more horrifying.

We never had such a dangerous cloud before...

My hope is that with the computer literacy that could become wide spread thanks to efforts like the Pi the next generation will have some faint idea about what is going on and how to fight back.

[John_Spikowski]

The cloud is a tornado that spins buzz words and fantasies.

[Heater]

When new technologies come along they are always surrounded by hype, buzz words and fantasies. As spun my those who want to make money out of it.

The dangers of every shady organization from governments to law enforcement to every other commercial/financial entity having access to every detail of everything you think, say and do are real enough.

[John_Spikowski]

The cloud works because there is no commitment. You can be anything you want to be as long as your CC doesn't decline.

[jcyr]

I'm not sure Bill Gates was the one who convinced the judges of the US justice system that computer software was a literary art which could be copyrighted as opposed to a mathematical algorithm which couldn't.

And yet I find very few that are mathematically liberated!

[John_Spikowski]

True.bits of the story which is are a byte in the ass.

[John_Spikowski]

Back on topic:

Am I correct by saying the following languages have Tatami 200 submissions?

C
Perl
ScriptBasic
8th