Liberation through Computer Literacy

[ejolson]

Full tatami challenge closure needs a star chart, in my opinion, which acknowledges all the challenge entries by awarding stars in three categories: time, memory use and lines of code.

In this modern post golden age of enlightenment shouldn't every child get a star?

That's absolutely correct. The fact that there are three categories guarantees a minimum of three stars per entry--unless cabbages are awarded instead.

[John_Spikowski]

I was hoping @jcjr would have posted a Swift example by now.

Fido has been working on a SuperPET entry and also one which uses the cc65 cross compiler. While that sounds a bit better than 64, that C compiler actually generates 6502 assembler.

Damn! You accept assembler entries? Was going to do one for the IBM 360, but then I thought assembler is not really a language, is it?

Oh, you must have missed the Oxygen Basic (Windows only) self compiling ASM BASIC.

[ejolson]

I was hoping @jcjr would have posted a Swift example by now.

Fido has been working on a SuperPET entry and also one which uses the cc65 cross compiler. While that sounds a bit better than 64, that C compiler actually generates 6502 assembler.

Damn! You accept assembler entries? Was going to do one for the IBM 360, but then I thought assembler is not really a language, is it?

Yes. From what I recall a bare-metal ARM assembler huge Fibonacci program was planned for in the original challenge. That program was never submitted, hopefully not because of health problems. With 360 assembler it should be possible to run it on the Pi using hardware emulation.

[Heater]

jcyr,

Language? I understood that the instruction set and microcode in the IBM 360 was big enough to be an operating system in it's own right

[John_Spikowski]

Weren't you doing Swift?

Actually it was bait for AIR. He took Swift for a spin on the AllBASIC forum. I guess his new job is consuming his free time.

Swift - Open Source Powerhouse

Swift looks to be the Linux of programming languages. When they went open source (big bang) there seemed to be a lot of interest by heavy weights. Nice to see it running on the RPi with GPIO support.

[DougieLawson]

With 360 assembler it should be possible to run it on the Pi using hardware emulation.

Hercules to the rescue!

If you're going down that route get the TK4- tur(n)key system. http://wotho.ethz.ch/tk4-/

It's also worth re-compiling Herc with GCC options to optimise it for the RPi model you're running it on. It then boots to a reasonably servicable MVS 3.8 system.

I've also had a Raspberry running UMMPS, HASP and MTS (and that's a very quirky thing). http://archive.michigan-terminal-system.org/

[ejolson]

If you're going down that route get the TK4- tur(n)key system. http://wotho.ethz.ch/tk4-/

Woohoo! Just in time for the American thanksgiving holiday.

Do you think additional vegetables should be included in the baskets for computing T(s)=n for larger values of n?

Here's a value of s such that T(s)=3000.

Code: Select all

T(12730028351040)=3000

Note I'm not certain that is the smallest value of s for which T(s)=3000. The run still has to finish checking all the other possibilities.

[John_Spikowski]

How much memory did that take?

[ejolson]

How much memory did that take?

Top currently reports

Code: Select all

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND   
21707 ejolson   20   0    6728   4524   1312 R 100.0   0.0  57:27.86 limited

so that tatami calculation is using about 4.5GB resident memory. That puts it just outside the reach of a 4GB Raspberry Pi, unless some tuning is done to make the prime table take less memory.

[John_Spikowski]

Good luck with your = 1000000 Tatami challenge. I satisfied the original challenge at 200 and looking to you to see what's next. If this is headed down absurdity lane then I'm investigating my time in the AllBASIC Array Class challenge.

My first project with the Judy extension module is to solve the insane anagram challenge with the Judy Hashing feature.

Stay tuned.

[Gavinmc42]

Heater, sounds like we followed a similar path towards computer literacy.
The more I learn the more I feel like I have just reached the equivalent of Computer Literacy comic books.
Some nice pictures with a few words.

And the rest of you lot are lost in delusional past memories of the good old days.
Emulate an IBM360? Er guys thousands of programmers worked on that over years.
And apparently Tatami mats are headed for extinction too.

If you guys get those old systems emulated on Pi's then you are Computer Literate to 1960-1990 levels?
I tried Oberon on a Pi, it looked just like an old Desktop OS.
Are all we good for is being historical re-enactors of old Computers as we slide towards dotage?
Doing the equivalent of making chain mail while Neural network guys play with the equivalent of machine guns?

But then to be compute literate do we need to pass through the history of computing to to catch up to the present?
Learn the history to understand the present?

From Basic to Swift.
Is Swift the future or the present of CL?
If you ignore Swift are you ignoring millions of iPhone users?
https://www.apple.com/au/everyone-can-code/

Has Apple noticed the same thing as Eben?
Is that why Swift has gone open?
Can iOS run on Pi's?
What is iOS? XNU kernel of Darwin!!!

Ouch - 1.4billion iPhones.
Have we missed the boat?
Is it too late to get Darwin on Pi's running Swift?
Or is iPadOS or MacOS a better choice?
Or do we just ignore those OS's because they are not open?

[John_Spikowski]

I think Swift is out to replace Python.

[Gavinmc42]

I think Swift is out to replace Python.

I am thinking the same thing.
Apple already has a large foothold in the Education market.
Schools here in Oz, it is Macbooks and/or iPads.

Could be too late for me but after seeing today's blog, perhaps a Pi kit under the tree for the kid might help him.
Make sure I know how to put Swift on it.
Will RPF's next OS come with Swift?

What is needed to be put on a Pi4 to write Android and Apple apps?
No point ignoring the two large elephants in the room any longer.

[John_Spikowski]

I think Swift deserves it's own language board.

[ejolson]

Code: Select all

// tatami-with-shift-shorts.c

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define nMax 100000000
#define nMaxSqrt sqrt(nMax)

unsigned short v[nMax / 2];

int Tatami(int s)
{
    for (int i = 7; i < nMaxSqrt; i += 2)
    {
        int k2 = i + 3;
        int k3 = i + i - 4;
        while ((k2 <= k3) && ((i * k2) < nMax))
        {
            int k4 = (nMax - 1) / i;
            if (k3 < k4)
                k4 = k3;
            for (int j = k2; j <= k4; j += 2)
                ++v[(i * j) / 2];
            k2 += i + 1;
            k3 += i - 1;
        }
    }
    for (int i = 8; i < nMaxSqrt; i += 2)
    {
        int k2 = i + 3;
        int k3 = i + i - 4;
        while ((k2 <= k3) && ((i * k2) < nMax))
        {
            int k4 = (nMax - 1) / i;
            if (k3 < k4)
                k4 = k3;
            for (int j = k2; j <= k4; ++j)
                ++v[(i * j) / 2];
            k2 += i + 1;
            k3 += i - 1;
        }
    }

    for (int i = 0; i < nMax / 2; ++i)
        if (v[i] == s)
            return i + i;
}

int main(int ac, char* av[])
{
    int s = atoi(av[1]);
    printf("T(%d) = %d\n", Tatami(s), s);
}

Despite all of this the task of figuring out the upper bound of V for any given s is still guess work.

I'm getting segfaults with the above code. Could you please check it?

[John_Spikowski]

A tailored Swift post.

[ejolson]

John_Spikowski,

The Tatami challenge is still in its early phase and mapping the universe will have to get in line.

ugh? I thought tatami was done already. I have seen all manner of solutions in a bunch of different languages go by here.

So plotting the Tatami rooms is off the table?

I finally convinced the former head of testing and code review to make a tatami-challenge star chart. It's possible Fido lost interest at some point, because the stars look a little strange to me. I think some programs are missing and it would be helpful for people to make note of any errors. At anyrate, pending additional funding from a large corporation, this seems to be as good as it gets for now.




For reference, the numbers next to the green represent runtime in seconds, red the memory in MB and yellow the lines of code used to solve the challenge. I'll provide a link to the source files in a following post.

Edit: The source files are now here.

[John_Spikowski]

ScriptBasic does Tatami 200 in 23 seconds on the RPi 4B 4GB.

Where did you get your numbers?

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	0m23.399s
user	0m23.267s
sys	0m0.121s
pi@RPi4B:~/sbrt/examples $ 

[ejolson]

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.

The Script Basic timings in the chart were from the above post. I see there are some better timings that were made more recently. I'll update the chart with the optimised tatamix version soon.

Would it be possible for you to do an

# apt-get install time

and then run all your entries on the Pi 4B using a command like

$ /usr/bin/time scriba tatamix.sb

to check the memory use as well?

[John_Spikowski]

Read the Transcript!

If you download the attached sriba.zip and ta,so.zip you can run it for yourself.

Please update the Python3 numbers as well. (see post following the above link)

After making the point ScriptBasic isn't the retard in the group. I believe ScriptBasic is the fattest interpreter in the group.

Thanks ejolson for updating your chart!


Laptop

Code: Select all

ubuntu@ubuntu:~/sbrt/examples$ /usr/bin/time scriba tatamix.sb 200
The smallest room size s for which T(s) = 200 is 85765680
4.62user 0.02system 0:04.65elapsed 99%CPU (0avgtext+0avgdata 51604maxresident)k
440inputs+16outputs (2major+24573minor)pagefaults 0swaps
ubuntu@ubuntu:~/sbrt/examples$ 

RPI 4B 4GB

Code: Select all

pi@RPi4B:~/sbrt/examples $ /usr/bin/time scriba tatamix.sb 200
The smallest room size s for which T(s) = 200 is 85765680
22.87user 0.18system 0:23.08elapsed 99%CPU (0avgtext+0avgdata 50508maxresident)k
560inputs+0outputs (1major+24532minor)pagefaults 0swaps
pi@RPi4B:~/sbrt/examples $ 

For Rust you need to talk to Heater.

Python 3

Code: Select all

pi@RPi4B:~/sbrt/examples $ /usr/bin/time ./tatami.py
The smallest room size s for which T(s) = 200 is 85765680
105.53user 0.18system 1:45.75elapsed 99%CPU (0avgtext+0avgdata 55940maxresident)k
8inputs+0outputs (0major+12958minor)pagefaults 0swaps
pi@RPi4B:~/sbrt/examples $ 

[ejolson]

RPI 4B 4GB

Code: Select all

pi@RPi4B:~/sbrt/examples $ /usr/bin/time scriba tatamix.sb 200
The smallest room size s for which T(s) = 200 is 85765680
22.87user 0.18system 0:23.08elapsed 99%CPU (0avgtext+0avgdata 50508maxresident)k
560inputs+0outputs (1major+24532minor)pagefaults 0swaps
pi@RPi4B:~/sbrt/examples $ 

The Python3, pypy and pypy3 results I managed to run myself. I ended up with a slightly faster timing, but pretty consistent with what you report above. I've updated the ScriptBasic entries, and corrected an error in the memory usage. Fido increased the resolution, but I'm not sure it looks better. The source code of all the challenge entries in the star chart are here.

[John_Spikowski]

Actually I would like to withdraw the extami.sb as that was WIP getting to the final version.

It would be nice to have a rating for readability and newbie friendly.

I think you should change your speed 'stars'.
1 = 1 to 9 seconds
2 = 10 to 29 seconds
3 = 30 to 49 seconds
4 = 50 >

[ejolson]

Actually I would like to withdraw the extami.sb as that was WIP getting to the final version.

It would be nice to have a rating for readability and newbie friendly.

I think you should change your speed 'stars'.
1 = 1 to 9 seconds
2 = 10 to 29 seconds
3 = 30 to 49 seconds
4 = 50 >

The suspiciously shaped stars are automatically assigned by percentiles as

• 5 stars for 80-100 percentile
• 4 stars for 60-80 percentile
• 3 stars for 40-60 percentile
• 2 stars for 20-40 percentile
• 1 star for 0-20 percentile.

Among other things, this means that as new challenge entries are recorded on the star chart the number of stars may change for other entries.

I think one of the more interesting things in the chart is how further optimisation improved the performance of the extami.sb program and would like to keep it for that reason. I added a comment to the source code (not included for the line counts used to make the start chart) to indicate that program was a work in progress that later resulted in mixtami.sb which ran faster. I hope that is okay.

[John_Spikowski]

If that's the case .maybe you should add the vtat.sb as well. (native SB array - only 100)

[gkreidl]

@ejolson: Please remove the pypy (Python2) results. Because of a bug in the index function of bytearrays it produces a wrong result. A python2/pypy version needs slightly modified code. I didn't care to publish it.