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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 2:41 pm

Hmmm....there seems to be a bug in the current stable rustc for ARM. No matter, it works with the nightly build:

On my Pi 3B

Code: Select all

$ rustup default nightly
info: using existing install for 'nightly-armv7-unknown-linux-gnueabihf'
info: default toolchain set to 'nightly-armv7-unknown-linux-gnueabihf'

  nightly-armv7-unknown-linux-gnueabihf unchanged - rustc 1.40.0-nightly (91fd6283e 2019-11-02)

pi@aalto-1:~/tatami $ rustc -O -o tatami_rs src/main.rs
pi@aalto-1:~/tatami $ gcc -Wall -O3 -o tatami_c tatami.c
tatami.c: In function ‘Tatami’:
tatami.c:35:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
pi@aalto-1:~/tatami $ time ./tatami_rs
The smallest room size s for which T(s) = 200 is 85765680

real    0m28.406s
user    0m28.129s
sys     0m0.270s
pi@aalto-1:~/tatami $ time ./tatami_c
The smallest room size s for which T(s) = 200 is 85765680

real    0m27.711s
user    0m27.502s
sys     0m0.200s
Can we get rid of that GCC warning ?
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 3:03 pm

jahboater wrote:
Sun Nov 03, 2019 9:45 am
bensimmo wrote:
Sun Nov 03, 2019 8:13 am
On a Pi4 they are pointless, the heat spreader and design mean a fan just blowing over it works best, heat is removed close to the source.
If you don't want a fan (for many obvious reasons) then a heat sink is useful.
Alas, if there had been a heatsink, then Fido's notes about tiling four-dimensional space time with Tatami cylinders would not have been ripped to shreds. As it is, I can't piece together the canine coder's calculation concerning the maximum valence of the dual graph and therefore the challenge remains two dimensional.

I wonder what area s corresponds to the first value of T(s) with a million digits?

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 3:13 pm

Heater wrote:
Sun Nov 03, 2019 2:41 pm
Can we get rid of that GCC warning ?
Its a clang warning.
But I now see all the compilers reasonably complain.
Fixed for C?

Code: Select all

// Tatami.c

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

#define nMax 100000000

static unsigned char v[nMax];

static int
Tatami( const int s )
{
    const int nMaxSqrt = sqrt(nMax);

    for (int i = 0; i < nMaxSqrt; ++i)
    {
        int k2, k3;
        for (int k = 1;
            (k2 = ((k * i) + k + 2)) <= (k3 = (((k + 1) * i) - k - 3));
            ++k)
        {
            if (i * k2 >= nMax)
                break;
            for (int j = k2; j <= k3; ++j)
            {
                if ((i & j & 1) || (i * j >= nMax))
                    continue;
                ++v[i * j];
            }
        }
    }

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

int main( void )
{
  const int result = Tatami(200);
  if( result < 0 )
    fprintf( stderr, "Tatami function error\n" );
  else
    printf( "The smallest room size s for which T(s) = 200 is %d\n", result );
}
On a Pi4 4GB

Code: Select all

$ time ./tatami
The smallest room size s for which T(s) = 200 is 85765680

real	0m10.109s
user	0m9.890s
sys	0m0.216s
$ 

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 3:39 pm

jcyr wrote:
Sun Nov 03, 2019 3:06 pm
ejolson wrote:
Sun Nov 03, 2019 3:03 pm
I wonder what area s corresponds to the first value of T(s) with a million digits?
Go find the problem's upper bound, then tell us why it won't run on a 4GB Pi.
Maybe the extreme memory use is because you are storing all values of T(s) up to the desired result.

What if one of those time traveling Tatami carpets took us back to the golden age of personal computing? Would it be possible to find s such that T(s)=200 using an 8-bit computer with 4K free memory? Is it possible the insolubility of the Tatami challenge on low-memory machines caused the widespread feelings of hopelessness responsible for the beginning of the digital dark ages?

I asked the lead developer of FidoBasic who growled, because your encabulator ate my graph paper, I'm not telling the correct value of the maximum valence in four dimensions. After a pause to scratch behind one ear, the dog developer continued. That time-traveling tour with K9 also visited five of the ten nearest events to the golden age of personal computing. I verified my Tatami challenge solution on the original 4K Commodore PET while eating raspberry pie.

Image
Last edited by ejolson on Sun Nov 03, 2019 3:59 pm, edited 1 time in total.

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 3:50 pm

jahboater,

Well, it's a GCC and clang warning where I live :)

This reminds me why C is so annoying.

jcyr quiets the warning by returning s and adding a helpful comment. That is essentially just returning some random number to keep the compiler happy.

jahboater's fix is to return an out of bad value, -1, as an error indication. Perhaps better.

Fixed for Rust. Using a proper return Result type that the makes the intention clear and the compiler will not let me forget to check:

Code: Select all

// Tatami in Rust

use std::result::Result;

const N_MAX: i32 = 100000000;

fn tatami(s: i32) -> Result<i32, String> {
    let mut v: Vec<u8> = vec![0; N_MAX as usize];

    let n_max_sqrt: i32 = (N_MAX as f64).sqrt() as i32;

    for i in 0..n_max_sqrt {
        let mut k2: i32;
        let mut k3: i32;

        let mut k: i32 = 1;
        loop {
            k2 = (k * i) + k + 2;
            k3 = ((k + 1) * i) - k - 3;
            if k2 > k3 {
                break;
            }
            if (i * k2) >= N_MAX {
                break;
            }
            for j in k2..=k3 {
                if (((i & j & 1) > 0)) || (i * j >= N_MAX) {
                    continue;
                }
                v[(i * j) as usize] += 1;
            }
            k += 1;
        }
    }
    for i in 0..N_MAX {
        if v[i as usize] == s as u8 {
            return Ok(i);
        }
    }
    Err("Oops! Should not get here".to_string())
}


fn main() {
    println!("The smallest room size s for which T(s) = 200 is {}", tatami(200).unwrap());
}
Now, I have translated jcyr's code from C to Rust with the comprehension of a Mechanical Turk.

What on Earth does it do? How does it work? Why are we doing this?

:)
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 4:40 pm

jahboater,
Why is this rust specific, you could just as easily write it in C could you not?
Quite likely one could hack something similar up. But not the way you have done it. The line:

Code: Select all

Err("Oops! Should not get here".to_string())
Would be a function call in C. Passing a string parameter. Or perhaps some kind of macro magic. That is not what is happening in that Rust code.

Firstly the return type of the tatami() function is specified as being a "Result" not a simple integer as before:

Code: Select all

fn tatami(s: i32) -> Result<i32, String> {
    ...
"Result" is an enumeration specified in the standard library. Of course enums in Rust are way more sophisticated than enums in C. They are not just a list of integer values. For example I could make my own result type with an enum:

Code: Select all

enum MyResult {
    Ok (i32),
    Err (String),
}
Here we see that the enum contains a thing called "Ok" and a thing called "Err". Those things have types of i32 and String respectively.

With that I can now return an enum value that contains the actual integer result I want to return. Or I can return the error enum value that contains the error message string. Either:

Code: Select all

return Ok(i);
or

Code: Select all

return Err("Oops! Should not get here".to_string());
With that return type the caller has to do something with that enum to get the actual integer result out. In a similar way one might use enums as cases in "switch" statements in C we can use enums in "match" statements in Rust:

Code: Select all

    match tatami(200) {
        Ok(i) => println!("The smallest room size s for which T(s) = 200 is {}", i),
        Err(mes) => println!("{}", mes),
    }
Such a match statement will not allow one to ignore any match conditions. So here we cannot forget to check the error condition.

In my code above I did not use "match". A quick short cut is to use "unwrap" to get the Ok value out.

Code: Select all

tatami(200).unwrap()
That unwrap() will panic and exit the program if the result is not Ok. Which is convenient for a quick experiment and you don't care to handle the error and continue.

To do something like this in C would require returning a struct that contains the result and the error condition. And then remembering to check that error condition.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 4:47 pm

Heater,
Thanks for the explanation - indeed rather good.
(I realized it was something cool like that and then deleted my post! sorry).

By the way, 204 is the largest value that it works for as far as I can see.

Its not an "impossible" situation, and the failure should be dealt with accordingly.
nMax needs to be increased.

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 5:11 pm

I suspected that is what happened. No worries.

When I run that rust tatami for 204 and 205 I now get:

Code: Select all

$ ./target/release/tatami
The smallest room size s for which T(s) = 204 is 73513440
Oops! Should not get here
I guess my message should rather indicate the reason for failure better.

But just now I have no idea what that code is doing or why it is doing it.

Yes, C mixes up the actual return values with error codes. One has to be careful the values of the error returns are all over the map. Its a mess.

Famously atoi() has no error detection at all!

By the way, that to_string() thing may seem odd. But the same issue arises in C++. A string in C++ is not the same as a std::String and often requires some messing around.

And consider:
char* s = "Hello";
s[2] = 'x';
Which results in the error:

Code: Select all

 warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
 char* s = "Hello";
Now you have to malloc a string or get yourself a std::String.

Or in C it's just undefined behavior....
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 5:14 pm

Heater wrote:
Sun Nov 03, 2019 3:50 pm
What on Earth does it do? How does it work? Why are we doing this?
Though the connection to yoga seems a bid absurd, my recollection is that yoga is the answer to your last question.

As to the mystery surrounding what the program does and how it works, that's the topic of literate programming

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

which, in my opinion, may not generally be as useful as yoga.

When I asked the dog developer about the Rust code, Fido stopped doing downward dog and growled: Those mutt keywords are discriminatory against all dogkind and they're not even spelled right. With a bark the canine continued, that scratchy cat is less offensive. Luckily, FidoBasic is nearly finished; I just need the Pi 4B again.

Unfortunately, I suspect FidoBasic is more likely to be finished in the sense of failed-project cancelled than anything else.

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 5:26 pm

Heater wrote:
Sun Nov 03, 2019 5:11 pm
Or in C it's just undefined behavior....
To be fair ...

Code: Select all

try.c: In function 'main':
try.c:20:15: error: initialization discards 'const' qualifier from pointer target type [-Werror=discarded-qualifiers]
20 |   char *s = "hello";
   |             ^~~~~
compilation terminated due to -Wfatal-errors.
Same as C++ by the look of it.

Literal strings go in the rodata (read-only data) segment and are typically shared so "hello" and "hello" are only stored once. The compiler cannot allow writing to that!

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 5:41 pm

Heater wrote:
Sun Nov 03, 2019 5:11 pm
Yes, C mixes up the actual return values with error codes. One has to be careful the values of the error returns are all over the map. Its a mess.
For library functions errno is entirely separate from the return value.
Linux system calls are not so clever. If it returns zero or positive then that is success, if it returns negative then its a failure (the value is negated and placed in errno).
Heater wrote:
Sun Nov 03, 2019 5:11 pm
Famously atoi() has no error detection at all!
Indeed, That why no one uses it any more (strtol() fixes all that), though I see its not officially deprecated.
atoi() must be over 60 years old!

Here is a 64-bit version by the way (runs fine on Pi/Raspbian):-

Code: Select all

// Tatami.c

#include <math.h>
#include <stdio.h>
#include <inttypes.h>

typedef int64_t i64;

#define nMax INT64_C(1000000000)

static unsigned char v[nMax];

static __attribute__((warn_unused_result)) i64
Tatami( const i64 s )
{
    const i64 nMaxSqrt = (i64)sqrt(nMax);

    for (i64 i = 0; i < nMaxSqrt; ++i)
    {
        i64 k2, k3;
        for (i64 k = 1;
            (k2 = ((k * i) + k + 2)) <= (k3 = (((k + 1) * i) - k - 3));
            ++k)
        {
            if (i * k2 >= nMax)
                break;
            for (i64 j = k2; j <= k3; ++j)
            {
                if ((i & j & 1) || (i * j >= nMax))
                    continue;
                ++v[i * j];
            }
        }
    }

    for (i64 i = 0; i < nMax; ++i)
        if (v[i] == s)
            return i;
    return -1;
}

int main( void )
{
  const i64 result = Tatami(210);
  if( result >= 0 )
    printf( "The smallest room size s for which T(s) = 210 is %" PRId64 "\n", result );
  else
    fprintf( stderr, "Tatami function size limit exceeded\n" );
}
Last edited by jahboater on Sun Nov 03, 2019 6:16 pm, edited 2 times in total.

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 5:54 pm

jcyr wrote:
Sun Nov 03, 2019 5:39 pm
What you have discovered is that there are no 205 tatamiless rectangles with an area of less than 100,000,002 square units.
Is there any larger value of s such that T(s)=205, or not?

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 6:02 pm

ejolson wrote:
Sun Nov 03, 2019 5:54 pm
jcyr wrote:
Sun Nov 03, 2019 5:39 pm
What you have discovered is that there are no 205 tatamiless rectangles with an area of less than 100,000,002 square units.
Is there any larger value of s such that T(s)=205, or not?
You mean?

Code: Select all

The smallest room size s for which T(s) = 205 is 102702600
As @jycr notes, finding the correct value for nMax is what is needed.

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 7:48 pm

jahboater,

To be fair:

Code: Select all

$ cat junk.c
int main (int argc, char* argv[]) {
    char* s = "Hello";
    s[2] = 'x';
    return 0;
}
$ gcc -Wall -O3 -o junk  junk.c
$
Produces no error or warning at all.
Literal strings go in the rodata (read-only data) segment and are typically shared so "hello" and "hello" are only stored once. The compiler cannot allow writing to that!
I know where literal strings go. So does the compiler I hope.

But the compiler silently allows you to continue into the swamp of undefined behavior that is C...
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 7:55 pm

jahboater,
For library functions errno is entirely separate from the return value.
Indeed. That is a whole other can of worms. Let's not go there...
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 7:59 pm

In the name of computer literacy is anyone going to explain what and how that tatami thing is doing what it does?

I never did understand the idea behind yoga, sushi, karaoke, kamikaze. Now I have tatami to add to my list of Japanese cultural items I don't understand.
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 8:30 pm

Heater wrote:
Sun Nov 03, 2019 7:59 pm
In the name of computer literacy is anyone going to explain what and how that tatami thing is doing what it does?

I never did understand the idea behind yoga, sushi, karaoke, kamikaze. Now I have tatami to add to my list of Japanese cultural items I don't understand.
My understanding is that yoga came from the Indian subcontinent.

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

The present Tatami code is getting around the need to factor s in T(s) by starting with all possible factors i*j and then incrementing T(i*j) when the dimensions don't admit a tiling by mats.

Due to memory constraints, such an approach would not work on the 8-bit machines from the golden age of personal computing, but one still has to wonder how much raspberry pie Fido and K9 ate while waiting for the result. Oh wait, they had a time machine.
Last edited by ejolson on Sun Nov 03, 2019 8:41 pm, edited 2 times in total.

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 8:32 pm

Hmm.. so I guess you are not in a hurry to explain the method.

If it took you weeks to figure it out it might take me months, years...

Just now, what I'd like to know is: How do we know that result is correct?

Often there is a way to verify an offered result even if one does not know how the result was arrived at. For example when finding prime factors or calculating huge numbers of digits of PI.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 8:35 pm

Heater wrote:
Sun Nov 03, 2019 7:48 pm
Produces no error or warning at all.
It is:

-Wwrite-strings

The difference is that its enabled by default for C++ but not for C.

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 8:57 pm

jahboater ,

OK, -Wwrite-strings it is.

Is there a comprehensive list of other warnings we should enable to avoid UB anywhere?

But I was thinking....

Where in the C language specification does it actually say I should not modify a string literal?

I look at section "6.4.5 String literals" it says:

7 It is unspecified whether these arrays are distinct provided their elements have the
appropriate values. If the program attempts to modify such an array, the behavior is
undefined.

So there we have it. No mention of "read only sections". No insistence that different string literals that happen to have the same character sequence get stored as only one string in some kind of ROM.

The syntactic and semantic definition of C totally allow you to do that.

Except, if you do that it's undefined behavior!

Really, I defy anyone to write even a single line of useful code in C that actually has a defined behavior!
Memory in C++ is a leaky abstraction .

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 9:20 pm

Heater wrote:
Sun Nov 03, 2019 8:57 pm
Where in the C language specification does it actually say I should not modify a string literal?

If the program attempts to modify such an array, the behavior is
undefined.
That's your answer :)
Its just the C and C++ way of doing things. Especially in C, they don't tend to absolutely forbid things, they just state that bad things are likely to happen if you do, so no one does (apart from beginners I suppose). It is been widely known for decades that writing to string literals is a bad idea.

const char *s = "hello";

The "const" gives you complete protection, no need to worry about the compiler warning flags:-

Code: Select all

$ gcc try.c 
try.c: In function 'main':
try.c:3:7: error: assignment of read-only location '*(s + 2)'
    3 |  s[2] = 'x';
      |       ^
$ 
No compiler flags at all, and the code is secure.

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

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 9:49 pm

jahboater,

Yes, it's the C way. I appreciate that. I think C is brilliant. A simple and elegant solution to the problem it was designed to solve. Enabling the rewriting of Unix from assembler to a higher level and importantly portable language.

I don't buy the idea that we should just blindly continue the practice 50 years later, and hand wave away it's problems, just because it's "the C way". Especially not when 70% of the recorded security vulnerabilities in software over recent years are traceable to trivial mistakes in memory use that a compiler/language system should be expected to find. As they were in the days of ALGOL back in the 1960s.

I'm not so tolerant of Stroustrup continuing the tradition of sloppy engineering into what should be a much higher level language in C++. If he were a structural engineer he would be facing a ton of lawsuits for incompetence and negligence.

Before anyone assumes otherwise, I'm not about to proclaim that Rust is the silver bullet to fix all our problems. Far from it. Rust does show however that there can be another way. A different way to look at things.

In what other field of science, engineering, mathematics, etc would such an attitude of "it's all undefined, but it's OK, the old hands know what they are doing, trust us" be tolerable?
Memory in C++ is a leaky abstraction .

jahboater
Posts: 5630
Joined: Wed Feb 04, 2015 6:38 pm
Location: West Dorset

Re: Liberation through Computer Literacy

Sun Nov 03, 2019 11:09 pm

Heater,

In (early) Fortran you could change the value of an integer literal.
That is, you could change 5 to have the value 6 when used.
(I think due to function arguments always being call-by-reference).
So "i = 5" left "i" with the value 6!!!!
Didn't stop Fortran being very popular and long lasting :)

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

Re: Liberation through Computer Literacy

Mon Nov 04, 2019 12:10 am

Yes, it's the C way. I appreciate that. I think C is brilliant. A simple and elegant solution to the problem it was designed to solve. Enabling the rewriting of Unix from assembler to a higher level and importantly portable language.
C is my hammer, screwdriver and cresent wrench. I can build almost anything with that but other tools make the job easier.

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

Re: Liberation through Computer Literacy

Mon Nov 04, 2019 4:58 am

Could someone translate this to a BASIC FOR/NEXT?

Code: Select all

        int k2, k3;
        for (int k = 1;
            (k2 = ((k * i) + k + 2)) <= (k3 = (((k + 1) * i) - k - 3));
            ++k)

Return to “General programming discussion”