Liberation through Computer Literacy

[ejolson]

Here are updated Tatami codes for PL/1, Fortran and 8th. I use ancient PL/1 compiler for Windows but it still produces the fastest code of the bunch. PL/1 code takes about 3 seconds to run, Fortran code doubles that time and runs in about 6.5 seconds.

I suspect the Fortran code would gain performance by using a one or two-byte integer data type for the v array. A similar optimisation could be done with my Visual Basic code.

It is likely the speed of the simple but memory intensive tatami.c algorithm is constrained by memory bandwidth. This makes it more of a memory benchmark than a test of processor speed. On the other hand, limited.c may depend more on processor speed and less on memory.

As searchs for plotting packages which create stars with tatami tilings as the background are coming up short, it looks like a new programming challenge may be in the making: Write a custom plotting program. I did, however, find



Could Minecraft be used to present the results of the tatami challenge?

[jcyr]

It is likely the speed of the simple but memory intensive tatami.c algorithm is constrained by memory bandwidth.

Not entirely. The 2 thread version achieve significant improvement.

Code: Select all

[email protected]:~/tatami $ g++ -march=native -mtune=cortex-a72 -O3 -o tatami tatami-threaded.cpp -lm -lpthread
[email protected]:~/tatami $ time ./tatami 400 1640000000
Running 1 thread
T(1639915200) = 400

real    4m35.925s
user    4m32.399s
sys     0m3.501s
[email protected]:~/tatami $ g++ -march=native -mtune=cortex-a72 -O3 -DTHREADED -o tatami tatami-threaded.cpp -lm -lpthread
[email protected]:~/tatami $ time ./tatami 400 1640000000
Running 2 threads
T(1639915200) = 400

real    3m31.191s
user    6m26.579s
sys     0m3.510s

But memory speed certainly is a factor.

Code: Select all

[email protected]:~/tatami$ g++ -march=native -mtune=cortex-a53 -O3 -o tatami tatami-threaded.cpp -lm -lpthread
[email protected]:~/tatami$ time ./tatami 400 1640000000
Running 1 thread
T(1639915200) = 400

real    2m37.296s
user    2m35.568s
sys     0m0.720s
[email protected]:~/tatami$ g++ -march=native -mtune=cortex-a53 -O3 -DTHREADED -o tatami tatami-threaded.cpp -lm -lpthread
[email protected]:~/tatami$ time ./tatami 400 1640000000
Running 2 threads
T(1639915200) = 400

real    1m48.448s
user    3m3.276s
sys     0m0.732s

Could Minecraft be used to present the results of the tatami challenge?

Go for it.

[jalih]

I suspect the Fortran code would gain performance by using a one or two-byte integer data type for the v array. A similar optimisation could be done with my Visual Basic code.

Fortran integer types are signed, 8-bit and 16 bit integers are nonstandard and might not be supported by all compilers. Some compilers also accepts unsigned integer types as an extension. I tested using (kind=2) 16 bit signed integer but it did not make any difference in program run time and my ide warned about possible loss of precision.

[jalih]

Here is a two threaded version of tatami for 8th:

Code: Select all

100000000 constant N-MAX
N-MAX n:sqrt n:int constant N-MAX-SQRT

N-MAX b:new true b:writable constant v

: swap+-  \ a b c f -- a (a+b+1) (a+c-1)
  drop
  swap 2 pick n:+ n:1+
  swap 2 pick n:+ n:1- ;

: l4  \ i k2 k3 k4 -- i k2 k3 k4
  \ i k2 k3 k4 j
  4 pick over n:*
  v over b:@ n:1+ rot swap b:! 2drop ;

: l3
  \ i
  dup 3 n:+             \ i k2=i+3
  over dup n:+ 4 n:-    \ i k2 k3=i+i-4
  repeat  \ i k2 k3
    2dup n:> not 2over n:* N-MAX n:< and if
      N-MAX n:1- 3 pick n:/ n:int     \  i k2 k3 k4
      2dup n:< if
        drop dup
      then
      ' l4 3 pick 2 pick loop   \ i k2 k3 k4
      swap+-
    else
      break
    then
  again
  2drop drop
  2 step ;

: l2  \ i k2 k3 k4 -- i k2 k3 k4
  \ i k2 k3 k4 j
  4 pick over n:*
  v over b:@ n:1+ rot swap b:! 2drop
  2 step ;

: l1
  \ i
  dup 3 n:+             \ i k2=i+3
  over dup n:+ 4 n:-    \ i k2 k3=i+i-4
  repeat  \ i k2 k3
    2dup n:> not 2over n:* N-MAX n:< and if
      N-MAX n:1- 3 pick n:/ n:int     \  i k2 k3 k4
      2dup n:< if
        drop dup
      then
      ' l2 3 pick 2 pick loop   \ i k2 k3 k4
      swap+-
    else
      break
    then
  again
  2drop drop
  2 step ;

: tatami  \ n -- s
  a:new
  ( ' l1 7 N-MAX-SQRT n:1- loop ) t:task a:push
  ( ' l3 8 N-MAX-SQRT n:1- loop ) t:task a:push
  t:wait
  v swap 1 a:close b:new b:search nip ;

: app:main
  200 tatami null? not if
    "The smallest room size s for which T(s) = 200 is %d.\n" s:strfmt .
  else
    drop "Not found\n" .
  then
  bye ;
  

[jcyr]

I looked up the definition of personal computer and found SCAMP: the Special Computer APL Machine Portable.

Sure, we all know what a personal computer is. But this thread is about personal computing, not personal computers.

What is the definition of personal computing?

[John_Spikowski]

I use my laptop for development. My phone is used for everything else.

[jcyr]

And we have Pascal. Borland's Turbo Pascal being the first practical compiled language for the venerable IBM PC.

Code: Select all

PROGRAM TatamiProgram;
USES crt;

VAR nMax : LONGWORD = 100000000;
VAR nMaxSqrt : LONGWORD;
VAR v : ARRAY OF WORD;
VAR t : LONGWORD;

FUNCTION tatami(t : LONGWORD) : LONGWORD;
VAR ix, i, j, k2, k3, k4 : LONGWORD;
BEGIN
   tatami := 0;
   nMaxSqrt := Trunc(Sqrt(Double(nMax)));
   SetLength(v, nMax);
   FOR i := 0 TO nMax - 1 DO
      v[i] := 0;

   i := 7;
   WHILE i < nMaxSqrt DO
   BEGIN
      k2 := i + 3;
      k3 := i + i - 4;
      WHILE (k2 <= k3) AND ((i * k2) < nMax) DO
      BEGIN
         k4 := (nMax - 1) DIV i;
         IF k3 < k4 THEN
            k4 := k3;
         j := k2;
         WHILE j <= k4 DO
         BEGIN
            ix := (i * j) DIV 2;
            v[ix] := v[ix] + 1;
            j := j + 2;
         END;
         k2 := k2 + i + 1;
         k3 := k3 + i - 1;
      END;
      i := i + 2;
   END;
   i := 8;
   WHILE i < nMaxSqrt DO
   BEGIN
      k2 := i + 3;
      k3 := i + i - 4;
      WHILE (k2 <= k3) AND ((i * k2) < nMax) DO
      BEGIN
         k4 := (nMax - 1) DIV i;
         IF k3 < k4 THEN
            k4 := k3;
         FOR j := k2 TO K4 DO
         BEGIN
            ix := (i * j) DIV 2;
            v[ix] := v[ix] + 1;
         END;
         k2 := k2 + i + 1;
         k3 := k3 + i - 1;
      END;
      i := i + 2;
   END;
   FOR i := 0 TO nMax DIV 2 DO
      IF v[i] = t THEN
      BEGIN
         tatami := i + i;
         EXIT;
      END;
END;

BEGIN
   t := 200;
   WriteLn('T(', tatami(t), ') = ', t);
END.

Code: Select all

[email protected]:~/tatami $ fpc -O3 tatami.pas  
Free Pascal Compiler version 3.0.4+dfsg-22+rpi1 [2019/02/04] for arm
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for ARMHF
Compiling tatami.pas
Assembling tatamiprogram
Linking tatami
/usr/bin/ld.bfd: warning: link.res contains output sections; did you forget -T?
71 lines compiled, 0.4 sec
[email protected]:~/tatami $ time ./tatami 
T(85765680) = 200

real    0m10.196s
user    0m9.691s
sys     0m0.502s

[John_Spikowski]

Could Minecraft be used to present the results of the tatami challenge?

Farm Sim may be a better choice. It has an object IDE and BASIC like scripting engine.

[John_Spikowski]

The V as a STRING idea didn't work out. There isn't an efficient way to replace a character within the string.

[John_Spikowski]

@jcyr,

It looks like you are using one instance of the V[] array for both threads, Is there no collisions due to each thread updates separate (odd / even) elements?

Can this be done in C rather than C++?

Is it possible to do multiple areas and combined them?

[Heater]

jcyr,

Sure, we all know what a personal computer is. But this thread is about personal computing, not personal computers.

What is the definition of personal computing?

Back in the dawn of time this lengthy thread opened with:

For those who have recently joined, the goal of this project is to determine

• What led to the end of the golden age of personal computing around the turn of the century?
• Could a suitable first programming language help ensure a second age of personal computing lasts?

Googling around I find definitions of "personal computing" like this:

Using desktop and laptop computers for personal use.

Not very helpful or even true anymore.

That definition says nothing about programming or programming languages or actually using as PC/laptop as a computer as such. Under that definition using a pc/laptop to play games, watch videos, socialize of Facebook are personal computing. Which I think is not quite the kind of activity ejolson had in mind.

Under that definition when I'm tinkering with Pi or Arduino or whatever micro-controllers and such I am not "personal computing", when I create software for my server instances in the cloud I am not "personal computing". My effort to create my own RISC V core in FPGA is not personal computing.

To my mind the golden age of personal computing ended with the death the the personal computer. Let me explain:

The Golden Age of Personal computing clearly started when we could get computers for ourselves for the first time with the creation of the micro-processor and the myriad of machines that were built with it. Machines that people owned and could do what they liked with. There was not much software around at the time so people set about learning to program and create their own. This was "personal computing".

As you know that huge diversity of personal computers died out with the arrival of the IBM PC and MSDOS/Windows. Moving to a world where one did not create ones own software or share ones creations with others. A world when the software one used was anything but personal. Down to the operating system it was owned and controlled by huge corporations.

The PC and the all dominating Windows were "Anti-Personal Computers". Not only killing off that huge diversity of the early personal computers it effectively killed off personal computing and the need/desire to acquire such skills.

The PC led the personal computing dark ages.

Which continues today. Most computers people own are now in phones, tablets, TVs etc. They are owned and controlled by mega corporations. They are anything but personal and their is little computing going on by the persons that own them.

On the bright side, thanks to Linux, the likes of the Pi and Arduino, the WEB, the world of Open Source and Free Software, there are almost certainly more people learning some programming and actually programming for themselves than ever there was during the "golden age".

[John_Spikowski]

Who would of guessed programming could be fun?

I just joined this forum in April and I'm on the 4 th page of top posting members. That includes being ban twice.

[ejolson]

I looked up the definition of personal computer and found SCAMP: the Special Computer APL Machine Portable.

Sure, we all know what a personal computer is. But this thread is about personal computing, not personal computers.

What is the definition of personal computing?

I also find this an interesting thread to go back and review. I suspect an attempt to define personal computing has happened a few times already. You've just inspired me to reread the thread myself.

The Golden Age of Personal computing clearly started when we could get computers for ourselves for the first time with the creation of the micro-processor and the myriad of machines that were built with it. Machines that people owned and could do what they liked with. There was not much software around at the time so people set about learning to program and create their own. This was "personal computing".

Agreed. For me an important feature of personal computing is that people write their own programs. I just came across the following invitation in the original documentation for the PET.



In the context of the second age of personal computing, one of the distinctive things about the Raspberry Pi is a renewed encouragement for users to write their own programs. Without that, how can owning a computer be liberating or even personal?

[John_Spikowski]

Computers are either an appliance or a toolbox. Will they ever cross paths?

[Heater]

ejolson,

That is an interesting tidbit of history.

In the context of the second age of personal computing, one of the distinctive things about the Raspberry Pi is a similar type of encouragement for users to write their own programs.

I have to take issue with your likening of that Commodore invitation to the motivation of the Pi.

Commodore there is clearly about making money. With that talk of "royalties". They clearly needed to get more software available to make their product more attractive. The end game of that is the closed source world and all it's licensing and copy protection, of corporate ownership of all software and hence our machines, of the dark ages of computing.

The Pi lives in the new world of Free and Open Source Software. Of personal creation and sharing. Of user collaboration.

Without that, how can owning a computer be liberating?

[jcyr]

As you know that huge diversity of personal computers died out with the arrival of the IBM PC and MSDOS/Windows. Moving to a world where one did not create ones own software or share ones creations with others. A world when the software one used was anything but personal. Down to the operating system it was owned and controlled by huge corporations.

The PC and the all dominating Windows were "Anti-Personal Computers". Not only killing off that huge diversity of the early personal computers it effectively killed off personal computing and the need/desire to acquire such skills.

The PC led the personal computing dark ages.

I completely disagree. The IBM PC was the first personal computer with serious mass market appeal and Windows furthered that. It wasn't just a novelty toy for geeks anymore. Furthermore it provided a common platform, allowing for the profitable distribution of of personally created software. Remember the Shareware idea? Worked profitably for me for about 15 years, all Windows based.

The open source movement seems to be to be in somewhat of a crisis presently. A lot of contributors are reaching the conclusion that it's a lot of work for little to no reward. The 'large corporations' you disdain are supporting more and more open source contributions.

The dark age began with the advent of the smart phone, not the IBM PC. The apocalypse looms...

[ejolson]

Commodore there is clearly about making money. With that talk of "royalties". They clearly needed to get more software available to make their product more attractive. The end game of that is the closed source world and all it's licensing and copy protection, of corporate ownership of all software and hence our machines, of the dark ages of computing.

While you were writing that post I changed the word similar to different and finally settled on renewed. You are right that the nature of the invitation for the PET owner to write software was more of a business deal than a direct promotion of computer literacy and fun. While the last line offers to send suggestions on programming techniques, the educational mission of the Raspberry Pi Foundation appears to be genuinely different.

I asked the lead developer of FidoBasic for an expert opinion, but the canine only whined, you mean there's no way to get rich quick by winning the tatami carpet challenge! What's the point of that?

[John_Spikowski]

The open source movement seems to be to be in somewhat of a crisis presently. A lot of contributors are reaching the conclusion that it's a lot of work for little to no reward. The 'large corporations' you disdain are supporting more and more open source contributions.

It's about doing something that outlast you. Legacies don't have a price tag. They're earned.

[ejolson]

I do not think that corporate-funded programmers working on open-source software is as big a problem as corporate-funded programmers not working on open-source software.

I completely disagree. The IBM PC was the first personal computer with serious mass market appeal and Windows furthered that.

According to Wikipedia

The Commodore 64 was one of the most popular microcomputers of its era, and is the best-selling model of home computer of all time.

https://en.m.wikipedia.org/wiki/Microcomputer

While that sounds like mass-market appeal to me, it's also true the IBM 5150 was so popular it defined what everyone now knows as the PC.

Another point of view is that the smart phone has actually created a renewed interest in computer programming. While such devices don't make very good phones, here they seem to have changed young people's perceptions about the general usefulness of understanding computer technology.

[Heater]

jcyr,

Remember the Shareware idea? Worked profitably for me for about 15 years, all Windows based.

I do indeed. And your statement totally supports my analysis of the situation rather than refuting it.

If I used your sharewhere, then you wrote it. You probably distributed it as closed source. You probably expected some return, as you say it was profitable.

Meanwhile I only used it. I learned nothing from it. You did the computing (in the context of ejolsons meaning) I did not.

What was a profitable era for you would have been part of the digital dark ages for me.

The open source movement seems to be to be in somewhat of a crisis presently. A lot of contributors are reaching the conclusion that it's a lot of work for little to no reward. The 'large corporations' you disdain are supporting more and more open source contributions.

Crisis? What crisis?

I see no crisis in the Free and Open source world. On the contrary it always amazes me to find that there is more and more high quality Free and Open Source software being created every day.

Firstly I don't have a disdain for large corporations. It's hard to imagine how we would survive without the organization of such entities. That does not mean I have to approve of all the products they push out or the ethics of all their activities.

Clearly if you are a lone hacker working hard in your basement on some software project that you distribute for free and hoping to make a living from you are likely on a hiding to nothing.

That is not what FOSS is all about. I doubt it ever was. It's a myth.

More realistically other things are going on:

1) Corporations are people too you know. They have needs for software of all kinds to support their business. Often there is a commonality in the kind of software they need. So rather than develop their own in house, which is expensive, or buy it from someone, which is a risky proposition, they found out it's often a good idea if they collaborate on development and support of what they need. So we find people being employed and paid handsomely by corporations to collaborate on Free and Open Source projects.

I'm pretty sure most of the Free and Open Source code I use comes into this category. From the OS to the data bases, to the web browsers to the language compilers, etc, etc...

2) Then there is the ocean of, shall we say, hobby projects. People are not contributing to them in order to earn a living. They collaborate to get something done just for fun.

[John_Spikowski]

Commitment is a promise to yourself. If you fail, you have no one else to blame.

[Heater]

The IBM PC killed personal computing.

Why? Because it was such a god damn awful bad machine nobody actually wanted to program it for fun.

You see, when micro-processors and the early personal computers arrived they were amazing. For the first time in history normal humans could own a computer at home. Fantastic. There was a lot of enthusiasm for them among the young generation at the time. There were new developments, new models coming out all the time. There was great anticipation of what was to come in the future.

Then came the IBM PC. It was awful. It was a retrograde step in many ways. It was totally uninspiring. Nobody could have fun programming that pile of junk. There is a reason there was a fanatical following for the likes of the Amiga and such. All those youngsters that were into computing for fun certainly did not want an IBM PC.

BUT the IBM PC had the attention of the corporate user. What with being IBM and all. So, the only people who had an interest in creating software for the IBM PC were those looking to make money out of it by selling software to those corporate users. And of course writing software for those hapless PC users that took their work home.

With economies and scale and the networking effects in play the IBM PC and clones took over everything, the diversity of the personal computer era died off.

Personal computing was dead, until the arrival of Linux.

[John_Spikowski]

The PC could replace mini computers (Rexon, MAI Basic4, ... OS & BASIC in one) at a fraction of the cost.

BASIC didn't come on the scene with Microsoft. It already had a mature user base.

[Heater]

John_Spikowski ,

BASIC didn't come on the scene with Microsoft. It already had a mature user base.

Yeah. I was already 20 years old when MS BASIC came out

Oh, wait, not me. I'd already moved on from BASIC at that time. Having discovered the joys of ALGOL.

[jcyr]

So, personal computing == programming? I find that a rather limited definition. Is an artist's use of Photoshop to illustrate, or an author's use of Word to write the next best seller, or my own use of Quicken to balance the books, not personal computing? Any interaction where one of the participants is a person is by definition personal.

Note that I used only commercial products in my examples. That's because it's what the majority of people use to personally compute in the real world. Most couldn't care less about the open source ideology, and prefer to pay for value - that value being a more sophisticated, polished and better integrated product only a governed, profit motivated entity can provide.

All this is supported by the Linux experience. Linux is king on server and cloud services where all the geeks toil, but on the desktop (or any other edge device) where normal people exist it is virtually unknown. Open source, like communism, is a great idea in theory but fails in practice.