Tatami Pi Fun.

[Heater]

Yay, I have a result on my Pi3 B, as 64 bit executable:

Code: Select all

$ cargo build --release
...
$ time target/release/tatami_rust
Pr40000=479909
T(63405342000)=1000
real    38m13.679s
user    38m13.231s
sys     0m0.049s

Which I think is at least correct.

Everything is i64 in this code. Might be worth tweaking that...

[Heater]

jcyr,

Most variable don't need to be 64 bits.

Of course.

As you've noticed for this particular case, 64 bit Pi is much better than 32 bit Pi.

It's not clear to me that I have noticed any such thing.

Last time I had comparable results 64 bits on the Pi was only about 30% faster than 32. Hardly worth shouting about.

However, I'm all for a 64 bit system on the Pi. This prune.c for example gives totally the wrong result when compiled and run on regular 32 bit Raspbian.

But hey, that is an undefined behavior of C in play there.

[Heater]

Speaking of which. We have been living with C/C++ for so many decades we start to think it actually makes sense. Well no, it has made us crazy.

Get this typical example:

Code: Select all

$ gcc -Wall -O3 -o prune prune.c
prune.c: In function ‘doinit’:
prune.c:16:14: warning: overflow in conversion from ‘long long int’ to ‘long int’ changes value from ‘100000000000’ to ‘1215752192’ [-Woverflow]
 #define smax 100000000000l
              ^~~~~~~~~~~~~
prune.c:49:10: note: in expansion of macro ‘smax’
     smin=smax;
          ^~~~

On what planet weird alien planet is that a "warning"?

It's a frikken error. Fair and square. No two ways about it. The program will not give the correct result.

This is absurd.

[ejolson]

@ejolson,

Try doing a diff between limited.c and prune.c, then comparing that to a diff between the two rusty programs.

Been there, done that. When every line has changed it's hard to tell what is what. I do wish people would use git if they are going to publish different, ever changing, versions of their code.

I compared the version of limited.c available at

http://fractal.math.unr.edu/~ejolson/pi ... /limited.c

to the version of wheel.c at

https://www.raspberrypi.org/forums/view ... 5#p1571059

to the version of prune.c at

https://www.raspberrypi.org/forums/view ... 5#p1573830

and obtained

Code: Select all

$ diff limited.c wheel.c 
1c1
< /*  limited.c -- Compute T(s) from Project Euler Problem 256
---
> /*  wheel.c -- Compute T(s) from Project Euler Problem 256
5c5,6
<     Avoid computing T(s) when s doesn't have enough factors.  */
---
>     Avoid computing T(s) when s doesn't have enough factors.
>     More sensible computation of prime table at startup.  */
21c22
< static int Pn,Tisn;
---
> static int Pn,Tisn,in;
35c36
<     for(i=0;i<Pn;i++){
---
>     for(i=1;i<in;i++){
37a39,42
>     for(i=in;P[i]*P[i]<=p;i++){
>         if(!(p%P[i])) return 0;
>     }
>     in=i-1;
44,45c49,50
<     P[0]=2; Pn=1;
<     for(p=3;Pn<Pnum;p++){
---
>     P[0]=2; P[1]=3; Pn=2, in=1;
>     for(p=5;Pn<Pnum;p+=2){

and then

Code: Select all

$ diff wheel.c prune.c
1,2c1,2
< /*  wheel.c -- Compute T(s) from Project Euler Problem 256
<     Written November 9, 2019 by Eric Olson in K&R C for PDP-11
---
> /*  prune.c -- Compute T(s) from Project Euler Problem 256
>     Written November 28, 2019 by Eric Olson in K&R C for PDP-11
6c6,7
<     More sensible computation of prime table at startup.  */
---
>     More sensible computation of prime table at startup.
>     Don't check larger values of s than already found.  */
15,17c16,18
< #define smax 100000000l
< #define Pnum 1300
< #define fnum 10
---
> #define smax 100000000000l
> #define Pnum 40000
> #define fnum 20
48c49
<     smin=smax+2;
---
>     smin=smax;
116c117
<     pmax=smax/s+1;
---
>     pmax=smin/s+1;
141c142
<     int n=200;
---
>     int n=1000;
142a144
>     printf("Pr(%d)=%ld\n",Pnum,P[Pnum-1]);

From what I call tell, these files diff pretty cleanly and only a few lines of code were touched in each case.

I now have a program from Fido which runs as

Code: Select all

$ OMP_STACKSIZE=4M time ./queue-openmp 
Pr(40000)=479909
T(63405342000)=1000
Lc=374
312.93user 0.05system 0:30.23elapsed 1035%CPU (0avgtext+0avgdata 151540maxresident)k
0inputs+0outputs (0major+37706minor)pagefaults 0swaps

on the Threadripper. Unfortunately, the source code didn't pass my review due to the use of dogarithms, malloc without free and the need to specify a 4MB stack size for each thread. It should also run on the Raspberry Pi. I've returned it for further revision.

[ejolson]

I now have a program from Fido which runs as

Code: Select all

$ OMP_STACKSIZE=4M time ./queue-openmp 
Pr(40000)=479909
T(63405342000)=1000
Lc=374
312.93user 0.05system 0:30.23elapsed 1035%CPU (0avgtext+0avgdata 151540maxresident)k
0inputs+0outputs (0major+37706minor)pagefaults 0swaps

Spot would be very interested in seeing Fido's OMP implementation.

Sounds good. As soon as the revisions are done I'll post the code.

[Heater]

This is not looking so good on the Pi:

On the x86-64 PC:

Code: Select all

$ time target/release/tatami_rust
Pr40000=479909
T(63405342000)=1000
real    5m58.546s
user    5m57.922s
sys     0m0.000s
$ time ./prune
Pr(40000)=479909
T(63405342000)=1000
real    4m48.525s
user    4m48.109s
sys     0m0.016s

On the Pi 3 B:

Code: Select all

$ time target/release/tatami_rust
Pr40000=479909
T(63405342000)=1000
real    38m22.279s
user    38m21.607s
sys     0m0.061s
$ time ./prune
Pr(40000)=479909
T(63405342000)=1000
real    21m54.700s
user    21m54.538s
sys     0m0.029s

[ejolson]

This is not looking so good on the Pi:

On the x86-64 PC:

Code: Select all

$ time target/release/tatami_rust
Pr40000=479909
T(63405342000)=1000
real    5m58.546s
user    5m57.922s
sys     0m0.000s
$ time ./prune
Pr(40000)=479909
T(63405342000)=1000
real    4m48.525s
user    4m48.109s
sys     0m0.016s

On the Pi 3 B:

Code: Select all

$ time target/release/tatami_rust
Pr40000=479909
T(63405342000)=1000
real    38m22.279s
user    38m21.607s
sys     0m0.061s
Pr(40000)=479909
T(63405342000)=1000
$ time ./prune
real    21m54.700s
user    21m54.538s
sys     0m0.029s

Let's see, for the PC

4.81/5.98=0.805

and for the Pi 3B

21.91/38.37=0.571

It appears that rust causes a 19.5 to 42.9 percent slowdown, a fact I can confirm with my car. I wonder how much of the difference is related to the in-order execution pipeline of the Cortex-A54 not being able to hide the cost of array-bounds range checking. Maybe the loss due to all those runtime checks would not be so dear on the 4B.

[Heater]

There in lies a whole rabbit hole of investigation. The whole warren in fact.

Firstly we are not comparing like with like yet. My Rust code does everything as i64 just now.

Then there is the whole issue of LLVM vs GCC code generation.

That's before we even think about what performance differences the language itself might impose.

Hopefully I will find some time to look in to that. And maybe I will be allowed a Pi 4 for Christmas.

Meanwhile...Do I get a cabbage?

[davidcoton]

Meanwhile...Do I get a cabbage?

Maybe a dog treat -- if Fido hasn't polished off the lot.

[ejolson]

Meanwhile...Do I get a cabbage?

Maybe it is time to make a new chart showing where things are. To do this I would need your latest code for solving T(s)=200. After that, what do you think about making a new T(s)=1000 chart?

For those who are following along, if you have improved, translated or written your own program to solve the T(s)=200 challenge, I'd be happy to include the results. I see there is a C++ version already posted here. Are there any programs I've missed between the transition from the previous thread to this one?

From my point of view, code written in Go, Haskell, Kotlin or Swift is interesting as well as programs which employ different algorithms or exhibit the use of novel techniques and language features. In particular, meta-programming, parallel programming and mixed language submissions are just fine. Any program that has been organized and carefully commented for literate clarity would likely lead to a greater understanding of what makes a suitable first programming language for beginners. As this is not a war, any language is welcome. However, to be forum friendly and included in the chart, the code must run on the Raspberry Pi.

[Heater]

ejolson,

Maybe it is time to make a new chart showing where things are.

I'm all for it.

To do this I would need your latest code for solving T(s)=200.

I'm on the case. Might take a day or two...

After that, what do you think about making a new T(s)=1000 chart?

Of course.

Any program that has been organized and carefully commented for literate clarity would likely lead to a greater understanding of what makes a suitable first programming language for beginners.

Cough.

[Heater]

jcyr,

Not sure I understand the point of translating the same few algorithms (which rely on the same underlying principles) to different programming languages? Fun for a while, but quickly gets old...

Not much point at all really. I have some excuses for wasting my time on it though. I have been learning Rust. In that respect I am a beginner. They claim it is a "systems programming language" that can be used where one might use C or C++. What better way to explore that claim than implementing something like ejolson's C solution in Rust? In my latest iteration of the solution I have been getting to grips with Rust's module system, which turns out to be not entirely obvious. I have also introduced some variable life time annotations, again a new concept and not entirely obvious to use. In short it's a learning exercise.

The Tatami problem is not a programming problem. It's more a mathematics or logic problem. The notion that something complicated can be made easily understood with a few comments, or many for that matter, seems a little far fetched and well beyond the scope of what beginners need. A beginner would focus on the syntax and semantics of a language, not the complexities of combinatorial algorithms.

I'm inclined to agree. Unlike our previous challenges this Tatami thing is not very accessible for mere mortals. Not me anyway.

Unless of course the only point is accumulating cabbages.

That is in fact the entire point of this thread

[ejolson]

The Tatami problem is not a programming problem. It's more a mathematics or logic problem. The notion that something complicated can be made easily understood with a few comments, or many for that matter, seems a little far fetched and well beyond the scope of what beginners need. A beginner should focus on the syntax and semantics of a language, not the complexities of combinatorial algorithms.

Unless of course the only point is accumulating cabbages.

While cabbage is good, it is also true that a bit of mathematics is needed to determine which rooms are impossible to auspiciously tile. Is that mathematics difficult to work out? I don't really know, because I didn't work it out myself. I drew pictures on paper for about an hour until I found a way to tile 6x10 and 8x10 rooms and thought I understood why the same approach didn't work for a 7x10 room. Then I read Dean Hickerson's note linked to in the post

https://www.raspberrypi.org/forums/view ... 5#p1560632

I don't know if John is still following this thread or not, but if he is, thanks for finding that note. Those pages covered the mathematics so I could proceed directly to the software engineering needed to write an efficient program. It also helped to look at the sample code included in the post

https://www.raspberrypi.org/forums/view ... 5#p1560751

While it sounds good to study syntax and semantics, my personal experience is that I cannot learn any programming language without actually writing a program. Similarly, I find it difficult to compare languages without writing code in both or at least reading code written by others. To keep our discussion of what makes a good first programming language based on fact, we actually write programs. The novelty of writing code to solve problems distinguishes what we do here from educational philosophy and theoretically prevents the eruption of a language war based on emotional attachments. From this point of view it is fortunate that a variety of programming languages and techniques can be used to solve the present challenge.

Although I believe the tatami challenge could be solved by someone who just learned programming, such submissions are notably missing. On the other hand, the entries in Rust were written by someone just learning that language as well as my entry in Visual Basic (for what that's worth). The same is true with Haskell, though the code has yet to be submitted. I've learned surprising things about C--also about profiling, OpenMP, MPI and the characteristics of particular compilers and hardware architectures. I'm a beginner when learning anything new and this forum has encouraged me to learn many new things.

[ejolson]

Unless of course the only point is accumulating cabbages.

That is in fact the entire point of this thread

I was looking at the list of suggested programming projects

https://projects.raspberrypi.org/en/projects

created by everyone's favorite computer company to see if there were any ideas that might help in our study of what makes a good first programming language. While Ada's Poetry Generator reminded my of Fido's doggerel project, it also seemed a little misleading about what type of program Ada Countess of Lovelace actually wrote in order that she be considered the first programmer ever.

Rather than random poetry, Ada wrote a program based on logic and mathematics which recursively computed the Bernoulli numbers. In my opinion, the realization that the first computer programmer was not only a woman but a person well versed in mathematical theory and computation acknowledges a role model that could help remove gender biases in science, technology, engineering and mathematics much more effectively than associating the same name with poetry randomly created. The latter association is, in fact, so absurd that if made during the 1800's it might have been considered libel. Indeed, when one studies Ada's poetical science one quickly discovers it was not whimsical or random, but closer to what is today called big-data analytics.

More information about the first non-trivial computer program and how it worked is available at

https://rclab.de/_media/analyticalengin ... k_v1.2.pdf

On another note, it is interesting that the store used in the analytical engine resulted in a variable type which was not easily overwritten. This likely led the Countess of Lovelace to make a particular choice concerning which algorithm to use when generating the Bernoulli numbers. Back on topic, similar considerations might be made by a modern Rust programmer when trying to minimize the number of mut variables in a code that solves tatami challenges.

[ejolson]

While cabbage is good, it is also true that a bit of mathematics is needed to determine which rooms are impossible to auspiciously tile.

Fido has been busy trying to get some more cabbages to grow in the snow. This task would appear difficult due to the lack of new tatami-challenge submissions. Fortunately there are no deadlines. In fact, programs which compute really big Fibonacci numbers and programs which find anagrams in the insane British dictionary are also welcome. In all cases, the corresponding charts will be updated, but only in the case of finding rectangles of the same area which do not admit tatami tilings will cabbage be awarded.

While waiting for the cabbage to grow I decided to read issue 88 of the MagPi. What attracted my attention was the feature article about retro computing. In particular, I wanted to know what to do with an emulated pet or even a real one. The article focused on emulating the ZX Spectrum but happily pointed to a complete archive of Ahoy! magazine for Commodore computers. As there was no sign of even a Brussels sprout poking through the snow, I clicked on the link to see what sort of peek and poke madness might lie in the premier issue of Ahoy!

Quite amusingly the Commodore 64 was on the front cover--an inexpensive PET replacement that hopefully doesn't eat as many dog treats. After skimming through a nice story on John von Neuman, I randomly clicked again and downloaded issue 16 which included an article on creating your own games complaining about peek and poke with a description on page 61 of what features the perfect home computer should have:

• Operating system in ROM.
• Sufficient RAM.
• Graphics that look good on a TV.
• Sound for 5-voice polyphony.
• Built-in BASIC.
• Fast reliable disk storage.
• Cartridge slots.

That just sets the stage, however, as the article finished with

The latest fashion in computer theory says that home computers don't have to be programmable anymore. Computer users just want software they can buy and run--they don't want to develop their own programs.

Well, the people who say that are the same people who sneer at BASIC because it's an "unstructured" language--you can do unpretty things with BASIC. You can get a 0 in neatness. What they don't realize is that the computer is supposed to make us free. Like the VCR, which lets us determine our own viewing schedule and even make our own TV programs, the computer is not in my home so that I can have only the programs that some company thinks at least 100,000 people will buy. There are sometimes things that only one person will buy--me. And I, for one, will own a computer that lets me create that program.

Could it be that this 1985 article is the well-spoken start of the liberation-through-computer-literacy movement? I wonder if today Orson has a Pi.

[Heater]

Orson Card (was he a Hollerith or what?) was not quoting "computer theory" there. He was telling how Bill Gates put it https://commons.wikimedia.org/wiki/File ... byists.jpg

Sadly he was a voice lost in the wind as the Personal Computer Winter closed in with the arrival of Windows.

I wonder if he got into Linux when things started to thaw out again?

While mathematics is good it should be remembered that it is totally founded on cabbage and other nutrient providing food stuffs.

[davidcoton]

... the Personal Computer Winter closed in with the arrival of Windows.

Personally I recommend closing Windows with the arrival of winter.

[Heater]

Ha, as they used to say "In a world without Windows, who needs Gates?"

[Heater]

Tatami results just in....

Code: Select all

prune (.c vs .rs)

On the x86-64 PC
----------------

gcc         -march=native -mtune=native     4m49s

rustc                                       4m58s

On the Pi 3B (64 bit) 
---------------------

gcc         -march=native -mtune=native     21m55s

rustc                                       26m11s

Once again Rust and C are pretty much neck and neck on the PC with Rust falling a bit behind on ARM.

Turns out I forgot to remove the arithmetic overflow checking in Rust. Sometimes you just have to take the safety wheels off.

At least we are in the same cabbage patch.

Code will be forthcoming...

[jahboater]

Turns out I forgot to remove the array bounds checking in Rust. Sometimes you just have to take the safety wheels off.

I thought that was Rust's raison d'être ?
Seems a shame to make it all unsafe and be as bad as C.

[Heater]

jahboater,

I thought that was Rust's raison d'être ?

Sorry, I said the wrong thing above. I meant "arithmetic overflow checking". I fixed it.

Whilst we are here....The safety guarantees in Rust are all about memory safety:

No use of uninitialized data.
No use of allocated data after it is freed.
No NULL pointer problems.
No data races between threads.
Etc, etc.

All done through Rusts model of ownership of data, data life time and immutable or mutable "borrowing of data".

All this happens no matter how you build your code, it's a static analysis done at compile time.

As a bonus there is also arithmetic overflow checking. Most of which is probably done at run time. Always enabled for debug builds. Can be optionally enabled for optimized release builds.

I forgot I had left an "overflow-checks = true" statement in my build file.

Durp, durp...

Even with the safety wheels of Rust can never be as bad as C with regard program correctness.

[Heater]

Yay!

Code: Select all

$ time ./prune
Pr(40000)=479909
T(63405342000)=1000

real    4m43.437s
user    4m43.203s
sys     0m0.016s
$ time target/release/tatami_rust
T(63405342000)=1000

real    4m43.769s
user    4m43.406s
sys     0m0.000s

[ejolson]

Yay!

Code: Select all

$ time ./prune
Pr(40000)=479909
T(63405342000)=1000

real    4m43.437s
user    4m43.203s
sys     0m0.016s
$ time target/release/tatami_rust
T(63405342000)=1000

real    4m43.769s
user    4m43.406s
sys     0m0.000s

I've got some good news and some bad news. The good news is that the snow had melted and I'm starting to see what looks like a crop of cabbages outside; the bad news is that code may not earn many cabbages in the runtime category.

[Heater]

Also runs on Pi 3B 64

Code: Select all

$ time target/release/tatami_rust
T(63405342000)=1000

real    24m46.845s
user    24m46.676s
sys     0m0.026s

$ time ./prune
Pr(40000)=479909
T(63405342000)=1000

real    21m55.181s
user    21m54.967s
sys     0m0.017s

Nothing much changed except cleaning it up to be presentable in public.

I'll settle for sprouts. I like sprouts.

[ejolson]

Orson Card (was he a Hollerith or what?)

It appears Orson is a science-fiction writer who published the book Ender's Game about the same time as writing that article for Ahoy! magazine. According to Wikipedia he is the only author to win the two top American prizes in science fiction literature consecutive years. Additional information is available at

http://www.hatrack.com/osc/about-more.shtml

There is also a long question answer section, but nobody asked whether he is a Hollerith or has a Raspberry Pi.

It looks like the technical writing stopped about the same time his science fiction became famous. According to the head of marketing and communications, Orson is first on the list of potential reviewers for the Beginners All-purpose RISC Komputer. While waiting for a BARK, maybe he could write an article for the MagPi.