jalih
Posts: 94
Joined: Mon Apr 15, 2019 3:54 pm

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 8:08 am

What is interesting that 8th version of tatami runs at least two times faster on my ROCK64 board than on my Windows PC machine. I will add OpenMP support to Fortran version and check if it helps...

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

Sun Nov 17, 2019 9:00 am

ScriptBasic vtat.sb

Code: Select all

' vtat.sb -- ScriptBasic translation of Eric Olson's VB code.

SUB Tinit(n)
  s_max = n - 1
  i_max = SQR(s_max) + 0.5
  SPLITA STRING(n, "0") BY "" TO T
  FOR i = 1 TO i_max
    j_min = i + 3
    j_max = 2 * i - 4
    WHILE i * j_min <= s_max AND j_min <= j_max
      FOR j = j_min TO j_max
        IF i * j <= s_max THEN
          T[i * j] = T[i * j] + 1
        END IF
      NEXT
      j_min = j_min + i + 1
      j_max = j_max + i - 1
    WEND
  NEXT
END SUB

FUNCTION Tinv(n)
  FOR s = 2 TO s_max STEP 2
    IF T[s] = n THEN 
      Tinv = s
      EXIT FUNCTION
    END IF
  NEXT
  Tinv = -1
END FUNCTION


Tinit(6700000)
PRINT FORMAT("T(%d) = 100", Tinv(100)),"\n"
Output

Code: Select all

pi@RPi4B:~/sbrt/examples $ /usr/bin/time ./scriba vtat.sb
T(6683040) = 100
96.40user 2.07system 1:38.54elapsed 99%CPU (0avgtext+0avgdata 940648maxresident)k
1224inputs+0outputs (4major+236437minor)pagefaults 0swaps
pi@RPi4B:~/sbrt/examples $ 
There is Petatmi.sb that does T(s) = 4.

Can you add the ta extension module C BASIC code?

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

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 4:20 pm

John_Spikowski wrote:
Sun Nov 17, 2019 9:00 am
Can you add the ta extension module C BASIC code?
The extension-module libraries written in C BASIC are already among the files here.
  • exface.c is for extat.sb
  • mixface.c is for mixtat.sb.
I renamed things so they appear next to each other in alphabetical order, but the matching is not obvious. I'll include further comments with the source code and a README file to indicate what is what. It's interesting that these are currently the only challenge entries using a bilingual approach. I wonder if Fido's SuperPET code will use any assembler.

One of the goals of this thread--in addition to tiling rooms with tatami carpets--is to determine a good first-programming language. The reason such a thing is important is because people who do not become professional software engineers seem to stick with the first language they learned. On the other hand, it may be possible to teach computer literacy using a polyglot approach with multiple languages from the beginning that can be combined together. Examples include
  • ScriptBasic with C
  • BBC Basic with Assembler
  • MATLAB with Fortran.
I asked the former vice-president of testing whether this seemed reasonable from an educational point of view. With a whine the dog developer responded, I've been trying to do that all day. How do you combine Scratch and Python together in the same project?
Last edited by ejolson on Sun Nov 17, 2019 5:53 pm, edited 2 times in total.

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 4:27 pm

Are these even the right answer?

Code: Select all

pi@raspberrypi:~/tatami $ gcc -O3 -march=native -mtune=cortex-a72 limited.c                              
pi@raspberrypi:~/tatami $ time ./a.out
T(1459731873600)=2000

real    337m12.286s
user    337m12.147s
sys     0m0.048s

Code: Select all

jcyr@jetson-nano:~/tatami$ gcc -O3 -mtune=cortex-a53 limited.c
jcyr@jetson-nano:~/tatami$ time ./a.out 2000
T(1459731873600)=2000

real    182m36.878s
user    182m13.356s
sys     0m0.148s
Also you're missing the Perl version

Code: Select all

pi@raspberrypi:~/tatami $ cat tatami.pl 
use feature ':5.10';

sub Tatami
{
  my ($arg1) = @_;
  use constant nMax => 100000000;
  use constant nMaxSqrt => int(sqrt(nMax));
  foreach my $i (7..nMaxSqrt - 1) {
    $k2 = $i + 3;
    $k3 = $i + $i - 4;
    foreach my $k ($k2..$k3) {
      last if (($i * $k2) >= nMax);
      $k4 = int(nMax / $i);
      if ($k3 < $k4) {
        $k4 = $k3;
      }
      if (($i & 1) == 1) {
        if (($k2 & 1) == 0) {
          for ($j = $k2; $j <= $k4; $j += 2) {
             $v[$i * $j]++;
          }
        }
      }
      else {
        foreach my $j ($k2..$k4) {
          $v[$i * $j]++;
        }
      }
      $k2 += $i + 1;
      $k3 += $i - 1;
    }
  }
  foreach my $i (0..nMax - 1) {
    if ($v[$i] == $arg1) {
      return $i;
    }
  }
}

say "The smallest room size s for which T(s) = 200 is ", Tatami(200);

pi@raspberrypi:~/tatami $ time perl tatami.pl
The smallest room size s for which T(s) = 200 is 85765680

real    1m49.715s
user    1m47.864s
sys     0m1.848s
It's um...uh...well it's kinda like...and it's got a bit of...

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 4:32 pm

Might I suggest a very minor optimization to limited.c? In doinit, change

Code: Select all

    for (p = 3; Pn < Pnum; p++)
        if (isprime(p))
            P[Pn++] = p;
to

Code: Select all

    for (p = 3; Pn < Pnum; p += 2)
        if (isprime(p))
            P[Pn++] = p;
It's um...uh...well it's kinda like...and it's got a bit of...

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

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 4:39 pm

jcyr wrote:
Sun Nov 17, 2019 4:27 pm
Are these even the right answer?

Code: Select all

pi@raspberrypi:~/tatami $ gcc -O3 -march=native -mtune=cortex-a72 limited.c                              
pi@raspberrypi:~/tatami $ time ./a.out
T(1459731873600)=2000

real    337m12.286s
user    337m12.147s
sys     0m0.048s
The Perl code has now been included in the star chart. Try refreshing the webpage or clearing your browser cache.

That's a good question whether

T(1459731873600)=2000

is the correct answer. On one hand, if I already knew the answer, what would be the point of computing it. On the other hand, if I don't already know the answer, how can I verify the computer program doesn't have any bugs. Some problems have answers that are easy to check but difficult to find. The tatami challenge appears to have answers that are easy to find but difficult to check.

Along those lines, any independent verification that s=1459731873600 is the smallest s such that T(s)=2000 would be greatly appreciated. If such a challenge generates enough entries, maybe Fido would make another star chart that actually has stars on it, or not.

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

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 4:56 pm

ejolson wrote:
Sun Nov 17, 2019 8:03 am
gkreidl wrote:
Sun Nov 17, 2019 7:48 am
@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.
Sorry, it seems I didn't notice that problem when I ran the code. You are right that wrong answers don't deserve any of those oddly shaped stars. Unfortunately, it will be a few hours before I can update the the chart. I'll ask Fido to remind me.
You are right. The output using pypy was

Code: Select all

$ /usr/bin/time pypy tatopt.py
No solution found for s=200 and nMax=100000000
Maximal T(s) found = 213 for room size = 91891800
18.08user 0.17system 0:18.28elapsed 99%CPU (0avgtext+0avgdata 85164maxresident)k
0inputs+0outputs (0major+15475minor)pagefaults 0swaps
which is clearly wrong. I have removed it from the star chart.

For reference the updated star chart is

Image
Image

I heard a commotion that sounded like a horde of zombies hacking on things coming from the dog house last night. After parallel codes in C++ and 8th, I wonder if another parallel challenge entry is about to be submitted.

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

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 5:33 pm

Aside:

I just rescued an old AMD Athlon II quad core 2.6MHz PC from it's trip to the dumpster.

Box is in good condition and amazingly it boots into Windows 7 Ultimate from it's 500GB HD. Thoughtfully the former owner has no password protection on it.

Anyway after a lengthy scrub and upgrade to Win 10, might as well make use of the licence right, and installing Debian under WSL it runs limited.c in 1.913 seconds.

Only narrowly beating the Pi 4 it seems.

Some how it has nearly 10 times the speed over WiFi to the internet than this much newer machine, grrr....
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 6:01 pm

Heater wrote:
Sun Nov 17, 2019 5:33 pm
Some how it has nearly 10 times the speed over WiFi to the internet than this much newer machine, grrr....
I think it is a really important point, that when recycling a previously used computer from a thrift store, junk yard or friend, one should fully wipe the disk before putting it back in service. Not only does this respect the previous user's privacy, but it prevents the new owner from being responsible for the legality of having access to any data that might have remained on the machine otherwise. Although this isn't the computer literacy of reading and writing programs, it is a type of digital street sense that, in my opinion, should be included in any introductory course about computers.

Was that Athlon II computer a notebook with built-in WiFi?

I wonder how fast it would be if you had installed Linux natively.

jalih
Posts: 94
Joined: Mon Apr 15, 2019 3:54 pm

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 7:20 pm

ejolson wrote:
Sun Nov 17, 2019 4:56 pm
After parallel codes in C++ and 8th, I wonder if another parallel challenge entry is about to be submitted.
Here is Fortran code with OpenMP directives giving a little speed boost...

Code: Select all

! Based on Tatami.c written by jcyr on Raspberrypi.org forums
program tatami
  use omp_lib
  
  implicit none

  integer, parameter :: N_MAX = 100000000
  integer, parameter :: N_MAX_SQRT = sqrt(real(N_MAX))

  integer :: ierror
  integer, dimension(:), allocatable :: v 

  integer :: i, j, k2, k3, k4

  allocate(v(0:N_MAX-1), stat=ierror)
  if (ierror /= 0) then
    print *, 'Could not allocate vector'
    stop
  end if

!$OMP PARALLEL DO PRIVATE(k2,k3,k4)
  do i = 7, N_MAX_SQRT - 1, 2
    k2 = i + 3
    k3 = i + i - 4
    do while((k2 <= k3) .and. ((i * k2) < N_MAX))
      k4 = (N_MAX - 1) / i
      if (k3 < k4) k4 = k3
      do j = k2, k4, 2
        v(i*j) = v(i*j) + 1
      end do
      k2 = k2 + i + 1
      k3 = k3 + i - 1
    end do    
  end do

!$OMP PARALLEL DO PRIVATE(k2,k3,k4)
  do i = 8, N_MAX_SQRT - 1, 2
    k2 = i + 3
    k3 = i + i - 4
    do while((k2 <= k3) .and. ((i * k2) < N_MAX))
      k4 = (N_MAX - 1) / i
      if (k3 < k4) k4 = k3
      do j = k2, k4, 1
        v(i*j) = v(i*j) + 1
      end do
      k2 = k2 + i + 1
      k3 = k3 + i - 1
    end do    
  end do
  
  do i = 0, N_MAX - 1, 1
    if (v(i) == 200) exit
  end do
    
  print *, 'The smallest room size s for which T(s) = 200 is:', i
  
  deallocate(v)  
end program tatami

jalih
Posts: 94
Joined: Mon Apr 15, 2019 3:54 pm

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 8:07 pm

Here is a little bit faster parallel version of tatami for 8th. I eliminated some stack juggling and added some task local variables:

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

: l4  \ i -- i
  \ i j
  2dup n:*
  v over b:@ n:1+ rot swap b:! 2drop ;

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

: l2  \ i -- i
  \ i j
  2dup n:*
  v over b:@ n:1+ rot swap b:! 2drop
  2 step ;

: l1
  \ i
  dup 3 n:+ "k2" t:!
  dup dup n:+ 4 n:- "k3" t:!
  repeat  \ i
    "k2" t:@ "k3" t:@ n:> not over "k2" t:@ n:* N-MAX n:< and if
      N-MAX n:1- over n:/ n:int "k4" t:! 
      "k3" t:@ "k4" t:@ n:< if
        "k3" t:@ "k4" t:!
      then
      ' l2 "k2" t:@ "k4" t:@ loop
      dup n:1+ "k2" t:@ n:+ "k2" t:!
      dup n:1- "k3" t:@ n:+ "k3" t:!
    else
      break
    then
  again
  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 ;
  

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

Re: Liberation through Computer Literacy

Sun Nov 17, 2019 9:14 pm

ejolson,

That is of course standard practice for all the reasons you mention and more. I like to start from a clean slate as it were.

However in this case you have caught me cheating. I did not wipe the disk first I simply fired up the Win 10 upgrade tool and trusted that when I checked the box that says it will remove all user data and setting and all installed applications etc that it does a good enough job.

I do have an excuse for this sloppy and shameful behavior, as poor as it may be...

On the blue Windows license sticker thing is the product key. I was hoping I could do my usual thing: Create an recovery DVD from a download from MS. Wipe the disk with a few passes of "dd if=/dev/urandom ...". Install a fresh Windows 7 from that recovery DVD using the product key. Then upgrade to Win 10.

However I was thwarted. One cannot get the recovery image from MS for that product key. It's some kind of OEM key. On entering the key on the download page it explained that I cannot do that and that I should get recovery media from the manufactured. HP in this case.

Well, I was not about to start faffing around asking HP for any such thing.

I googled around and found that there ways around this problem. They all looked rather shady to me. I really don't like to use images, binaries, tools from web sites I have never heard of. I have no idea about the legality of it even.

So, I followed only option MS provides. Update the thing in place. Which at least looks squeaky clean and new when you are done. No users except me. No data anywhere to be seen.

Hmm... I hear you saying: "There will be some old user data lurking on sectors of the disk. You should not assume the upgrade wiped over everything"

Very true. Perhaps I should now start filling it up with files of random data to obliterate whatever is there as best I can...
Although this isn't the computer literacy of reading and writing programs, it is a type of digital street sense that, in my opinion, should be included in any introductory course about computers.
I totally agree.

In this case MS has gone out of it's way to actively prevent such digital hygiene.
Was that Athlon II computer a notebook with built-in WiFi?
Notebook! This a good old tower box. Not so big but weighs a ton.

Turns out it was not WiFi at all. I forgot I plugged in an ethernet cable last night! Pretty sweet to be reminded that I do actually have 100Mbs connection here.
I wonder how fast it would be if you had installed Linux natively.
I doubt it would make much difference. It's the same gcc, generating the same code is it not?
Memory in C++ is a leaky abstraction .

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 12:59 am

ejolson wrote:
Sun Nov 17, 2019 4:56 pm
After parallel codes in C++ and 8th, I wonder if another parallel challenge entry is about to be submitted.
Can limited.c be parallelized?
It's um...uh...well it's kinda like...and it's got a bit of...

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 1:04 am

A parallel code challenge

Given the CRC64 function below, find the smallest integer value of I, such that CRC64(I) is less than or equal to 30000.

Code: Select all

static const uint64_t crc64_tab[256] = {
    0x0000000000000000LL, 0x7ad870c830358979LL, 0xf5b0e190606b12f2LL, 0x8f689158505e9b8bLL,
    0xc038e5739841b68fLL, 0xbae095bba8743ff6LL, 0x358804e3f82aa47dLL, 0x4f50742bc81f2d04LL,
    0xab28ecb46814fe75LL, 0xd1f09c7c5821770cLL, 0x5e980d24087fec87LL, 0x24407dec384a65feLL,
    0x6b1009c7f05548faLL, 0x11c8790fc060c183LL, 0x9ea0e857903e5a08LL, 0xe478989fa00bd371LL,
    0x7d08ff3b88be6f81LL, 0x07d08ff3b88be6f8LL, 0x88b81eabe8d57d73LL, 0xf2606e63d8e0f40aLL,
    0xbd301a4810ffd90eLL, 0xc7e86a8020ca5077LL, 0x4880fbd87094cbfcLL, 0x32588b1040a14285LL,
    0xd620138fe0aa91f4LL, 0xacf86347d09f188dLL, 0x2390f21f80c18306LL, 0x594882d7b0f40a7fLL,
    0x1618f6fc78eb277bLL, 0x6cc0863448deae02LL, 0xe3a8176c18803589LL, 0x997067a428b5bcf0LL,
    0xfa11fe77117cdf02LL, 0x80c98ebf2149567bLL, 0x0fa11fe77117cdf0LL, 0x75796f2f41224489LL,
    0x3a291b04893d698dLL, 0x40f16bccb908e0f4LL, 0xcf99fa94e9567b7fLL, 0xb5418a5cd963f206LL,
    0x513912c379682177LL, 0x2be1620b495da80eLL, 0xa489f35319033385LL, 0xde51839b2936bafcLL,
    0x9101f7b0e12997f8LL, 0xebd98778d11c1e81LL, 0x64b116208142850aLL, 0x1e6966e8b1770c73LL,
    0x8719014c99c2b083LL, 0xfdc17184a9f739faLL, 0x72a9e0dcf9a9a271LL, 0x08719014c99c2b08LL,
    0x4721e43f0183060cLL, 0x3df994f731b68f75LL, 0xb29105af61e814feLL, 0xc849756751dd9d87LL,
    0x2c31edf8f1d64ef6LL, 0x56e99d30c1e3c78fLL, 0xd9810c6891bd5c04LL, 0xa3597ca0a188d57dLL,
    0xec09088b6997f879LL, 0x96d1784359a27100LL, 0x19b9e91b09fcea8bLL, 0x636199d339c963f2LL,
    0xdf7adabd7a6e2d6fLL, 0xa5a2aa754a5ba416LL, 0x2aca3b2d1a053f9dLL, 0x50124be52a30b6e4LL,
    0x1f423fcee22f9be0LL, 0x659a4f06d21a1299LL, 0xeaf2de5e82448912LL, 0x902aae96b271006bLL,
    0x74523609127ad31aLL, 0x0e8a46c1224f5a63LL, 0x81e2d7997211c1e8LL, 0xfb3aa75142244891LL,
    0xb46ad37a8a3b6595LL, 0xceb2a3b2ba0eececLL, 0x41da32eaea507767LL, 0x3b024222da65fe1eLL,
    0xa2722586f2d042eeLL, 0xd8aa554ec2e5cb97LL, 0x57c2c41692bb501cLL, 0x2d1ab4dea28ed965LL,
    0x624ac0f56a91f461LL, 0x1892b03d5aa47d18LL, 0x97fa21650afae693LL, 0xed2251ad3acf6feaLL,
    0x095ac9329ac4bc9bLL, 0x7382b9faaaf135e2LL, 0xfcea28a2faafae69LL, 0x8632586aca9a2710LL,
    0xc9622c4102850a14LL, 0xb3ba5c8932b0836dLL, 0x3cd2cdd162ee18e6LL, 0x460abd1952db919fLL,
    0x256b24ca6b12f26dLL, 0x5fb354025b277b14LL, 0xd0dbc55a0b79e09fLL, 0xaa03b5923b4c69e6LL,
    0xe553c1b9f35344e2LL, 0x9f8bb171c366cd9bLL, 0x10e3202993385610LL, 0x6a3b50e1a30ddf69LL,
    0x8e43c87e03060c18LL, 0xf49bb8b633338561LL, 0x7bf329ee636d1eeaLL, 0x012b592653589793LL,
    0x4e7b2d0d9b47ba97LL, 0x34a35dc5ab7233eeLL, 0xbbcbcc9dfb2ca865LL, 0xc113bc55cb19211cLL,
    0x5863dbf1e3ac9decLL, 0x22bbab39d3991495LL, 0xadd33a6183c78f1eLL, 0xd70b4aa9b3f20667LL,
    0x985b3e827bed2b63LL, 0xe2834e4a4bd8a21aLL, 0x6debdf121b863991LL, 0x1733afda2bb3b0e8LL,
    0xf34b37458bb86399LL, 0x8993478dbb8deae0LL, 0x06fbd6d5ebd3716bLL, 0x7c23a61ddbe6f812LL,
    0x3373d23613f9d516LL, 0x49aba2fe23cc5c6fLL, 0xc6c333a67392c7e4LL, 0xbc1b436e43a74e9dLL,
    0x95ac9329ac4bc9b5LL, 0xef74e3e19c7e40ccLL, 0x601c72b9cc20db47LL, 0x1ac40271fc15523eLL,
    0x5594765a340a7f3aLL, 0x2f4c0692043ff643LL, 0xa02497ca54616dc8LL, 0xdafce7026454e4b1LL,
    0x3e847f9dc45f37c0LL, 0x445c0f55f46abeb9LL, 0xcb349e0da4342532LL, 0xb1eceec59401ac4bLL,
    0xfebc9aee5c1e814fLL, 0x8464ea266c2b0836LL, 0x0b0c7b7e3c7593bdLL, 0x71d40bb60c401ac4LL,
    0xe8a46c1224f5a634LL, 0x927c1cda14c02f4dLL, 0x1d148d82449eb4c6LL, 0x67ccfd4a74ab3dbfLL,
    0x289c8961bcb410bbLL, 0x5244f9a98c8199c2LL, 0xdd2c68f1dcdf0249LL, 0xa7f41839ecea8b30LL,
    0x438c80a64ce15841LL, 0x3954f06e7cd4d138LL, 0xb63c61362c8a4ab3LL, 0xcce411fe1cbfc3caLL,
    0x83b465d5d4a0eeceLL, 0xf96c151de49567b7LL, 0x76048445b4cbfc3cLL, 0x0cdcf48d84fe7545LL,
    0x6fbd6d5ebd3716b7LL, 0x15651d968d029fceLL, 0x9a0d8ccedd5c0445LL, 0xe0d5fc06ed698d3cLL,
    0xaf85882d2576a038LL, 0xd55df8e515432941LL, 0x5a3569bd451db2caLL, 0x20ed197575283bb3LL,
    0xc49581ead523e8c2LL, 0xbe4df122e51661bbLL, 0x3125607ab548fa30LL, 0x4bfd10b2857d7349LL,
    0x04ad64994d625e4dLL, 0x7e7514517d57d734LL, 0xf11d85092d094cbfLL, 0x8bc5f5c11d3cc5c6LL,
    0x12b5926535897936LL, 0x686de2ad05bcf04fLL, 0xe70573f555e26bc4LL, 0x9ddd033d65d7e2bdLL,
    0xd28d7716adc8cfb9LL, 0xa85507de9dfd46c0LL, 0x273d9686cda3dd4bLL, 0x5de5e64efd965432LL,
    0xb99d7ed15d9d8743LL, 0xc3450e196da80e3aLL, 0x4c2d9f413df695b1LL, 0x36f5ef890dc31cc8LL,
    0x79a59ba2c5dc31ccLL, 0x037deb6af5e9b8b5LL, 0x8c157a32a5b7233eLL, 0xf6cd0afa9582aa47LL,
    0x4ad64994d625e4daLL, 0x300e395ce6106da3LL, 0xbf66a804b64ef628LL, 0xc5bed8cc867b7f51LL,
    0x8aeeace74e645255LL, 0xf036dc2f7e51db2cLL, 0x7f5e4d772e0f40a7LL, 0x05863dbf1e3ac9deLL,
    0xe1fea520be311aafLL, 0x9b26d5e88e0493d6LL, 0x144e44b0de5a085dLL, 0x6e963478ee6f8124LL,
    0x21c640532670ac20LL, 0x5b1e309b16452559LL, 0xd476a1c3461bbed2LL, 0xaeaed10b762e37abLL,
    0x37deb6af5e9b8b5bLL, 0x4d06c6676eae0222LL, 0xc26e573f3ef099a9LL, 0xb8b627f70ec510d0LL,
    0xf7e653dcc6da3dd4LL, 0x8d3e2314f6efb4adLL, 0x0256b24ca6b12f26LL, 0x788ec2849684a65fLL,
    0x9cf65a1b368f752eLL, 0xe62e2ad306bafc57LL, 0x6946bb8b56e467dcLL, 0x139ecb4366d1eea5LL,
    0x5ccebf68aecec3a1LL, 0x2616cfa09efb4ad8LL, 0xa97e5ef8cea5d153LL, 0xd3a62e30fe90582aLL,
    0xb0c7b7e3c7593bd8LL, 0xca1fc72bf76cb2a1LL, 0x45775673a732292aLL, 0x3faf26bb9707a053LL,
    0x70ff52905f188d57LL, 0x0a2722586f2d042eLL, 0x854fb3003f739fa5LL, 0xff97c3c80f4616dcLL,
    0x1bef5b57af4dc5adLL, 0x61372b9f9f784cd4LL, 0xee5fbac7cf26d75fLL, 0x9487ca0fff135e26LL,
    0xdbd7be24370c7322LL, 0xa10fceec0739fa5bLL, 0x2e675fb4576761d0LL, 0x54bf2f7c6752e8a9LL,
    0xcdcf48d84fe75459LL, 0xb71738107fd2dd20LL, 0x387fa9482f8c46abLL, 0x42a7d9801fb9cfd2LL,
    0x0df7adabd7a6e2d6LL, 0x772fdd63e7936bafLL, 0xf8474c3bb7cdf024LL, 0x829f3cf387f8795dLL,
    0x66e7a46c27f3aa2cLL, 0x1c3fd4a417c62355LL, 0x935745fc4798b8deLL, 0xe98f353477ad31a7LL,
    0xa6df411fbfb21ca3LL, 0xdc0731d78f8795daLL, 0x536fa08fdfd90e51LL, 0x29b7d047efec8728LL
};

uint64_t crc64(uint64_t value) {
    char* s = (char*)&value;
    uint64_t crc = 0x12345678abcdef01LL;
    for (uint32_t j = 0; j < 8; j++)
        crc = crc64_tab[(uint8_t)crc ^ (*s++)] ^ (crc >> 8);
    return crc;
}
For example: 131064095261 is the smallest integer where CRC64(131064095261) is less than or equal to 100000000.
Last edited by jcyr on Mon Nov 18, 2019 2:16 am, edited 3 times in total.
It's um...uh...well it's kinda like...and it's got a bit of...

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

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 1:08 am

jcyr wrote:
Mon Nov 18, 2019 12:59 am
ejolson wrote:
Sun Nov 17, 2019 4:56 pm
After parallel codes in C++ and 8th, I wonder if another parallel challenge entry is about to be submitted.
Can limited.c be parallelized?
I suspect it would scale pretty well because how localised the memory references are when it's running.

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

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 1:49 am

Heater wrote:
Sun Nov 17, 2019 9:14 pm
I doubt it would make much difference. It's the same gcc, generating the same code is it not?
I was thinking about the speed of the network and possibly avoiding an additional layer of emulation by running Linux natively.

Now that you have updated to Windows 10, is it possible to burn a recovery disk and then properly wipe the hard drive?

On the other hand, since you already have a good enough Windows computer, maybe installing Dragonfly, Free, Net or Open BSD would be more useful. I personally think DragonflyBSD is the most interesting, partly because of Matt's computer literacy and general perspective on parallel and distributed systems.

Dragonfly is also the only BSD that doesn't run on the Raspberry Pi. Unfortunately, porting it--though not having anything to do with encryption--does not seem like a good beginners' programming challenge for this thread.

jcyr
Posts: 504
Joined: Sun Apr 23, 2017 1:31 pm
Location: Atlanta

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 2:27 am

ejolson wrote:
Mon Nov 18, 2019 1:49 am
Dragonfly is also the only BSD that doesn't run on the Raspberry Pi.
They've hacked so much of it, can it still be called BSD?
It's um...uh...well it's kinda like...and it's got a bit of...

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

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 2:47 am

jalih wrote:
Sun Nov 17, 2019 7:20 pm
ejolson wrote:
Sun Nov 17, 2019 4:56 pm
After parallel codes in C++ and 8th, I wonder if another parallel challenge entry is about to be submitted.
Here is Fortran code with OpenMP directives giving a little speed boost...
On the Raspberry Pi 4B the runs

Code: Select all

$ /usr/bin/time ./tatomp-f90 
 The smallest room size s for which T(s) = 200 is:    85765680
27.83user 2.10system 0:10.61elapsed 281%CPU (0avgtext+0avgdata 392056maxresident)k
720inputs+0outputs (3major+195598minor)pagefaults 0swaps
$ /usr/bin/time ./tatomp-f90 
 The smallest room size s for which T(s) = 200 is:    85765680
27.81user 2.10system 0:10.60elapsed 282%CPU (0avgtext+0avgdata 392128maxresident)k
0inputs+0outputs (0major+195537minor)pagefaults 0swaps
$ /usr/bin/time ./tatomp-f90 
 The smallest room size s for which T(s) = 200 is:    85765680
27.76user 2.12system 0:10.60elapsed 281%CPU (0avgtext+0avgdata 391960maxresident)k
0inputs+0outputs (0major+195699minor)pagefaults 0swaps
indicate that a 2.8 fold increase in CPU utilization leads to a 1.34 times increase in speed. The star chart has been updated with the new challenge entry.

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

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 3:06 am

I just realized that I forgot to include the original tatami.c code from the post

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

upon which so many of the other programs are based. When run on the Pi 4B I obtained

Code: Select all

$ wc tatami.c 
 40 131 780 tatami.c
$ /usr/bin/time ./tatami
The smallest room size s for which T(s) = 200 is 85765680
10.06user 0.32system 0:10.41elapsed 99%CPU (0avgtext+0avgdata 98992maxresident)k
0inputs+0outputs (0major+48905minor)pagefaults 0swaps
$ /usr/bin/time ./tatami
The smallest room size s for which T(s) = 200 is 85765680
10.01user 0.35system 0:10.39elapsed 99%CPU (0avgtext+0avgdata 98936maxresident)k
0inputs+0outputs (0major+48903minor)pagefaults 0swaps
$ /usr/bin/time ./tatami
The smallest room size s for which T(s) = 200 is 85765680
10.08user 0.32system 0:10.43elapsed 99%CPU (0avgtext+0avgdata 98896maxresident)k
0inputs+0outputs (0major+48902minor)pagefaults 0swaps
which indicates
  • elapsed time=10.39 seconds
  • resident memory=96.578 MB
  • lines of code=40 lines.
The star chart has been updated to include tatami.c

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 18, 2019 3:36 am

Closing Statement

If you only count the ScriptBasic code, I'm at 35 lines making it the smallest code base / memory usage for an array based submission and only 10 to 15 seconds slower then the compiled group. We failed to touch on readability and ease of use.

Should code lines of shared object library be counted? If so please add up the include lines of code for the other submissions.

I'm wondering if a ScriptBasic to C BASIC translator would be worthwhile. Based on these results I'm having a hard time with justification. The extension module interface typically fills any performance holes.

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

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 6:51 am

ejolson,
I was thinking about the speed of the network and possibly avoiding an additional layer of emulation by running Linux natively.
There is no emulation going on in the Linux Subsystem for Windows. It runs the same binaries as Debian, in this case, for x86-64 natively. The WSL only provides all the Linux kernel calls and gets Windows to do them.
Now that you have updated to Windows 10, is it possible to burn a recovery disk and then properly wipe the hard drive?
That is an interesting thought.

I have made a number of Win 10 recovery disks after installations before. So far I have never checked that they actually work!
On the other hand, since you already have a good enough Windows computer, maybe installing Dragonfly, Free, Net or Open BSD would be more useful.
Every few years for a long time I have tried installing some BSD or other on a spare PC that was passing by. So far I have never managed to get one to install or and boot.

I have only ever seen one instance of BSD running on a PC. Many years ago. I always wondered how the guy did it.

As much as I love the BSD idea I'm not about to go down that rabbit hole.
Memory in C++ is a leaky abstraction .

jalih
Posts: 94
Joined: Mon Apr 15, 2019 3:54 pm

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 7:54 am

Heater wrote:
Mon Nov 18, 2019 6:51 am
Every few years for a long time I have tried installing some BSD or other on a spare PC that was passing by. So far I have never managed to get one to install or and boot.

I have only ever seen one instance of BSD running on a PC. Many years ago. I always wondered how the guy did it.

As much as I love the BSD idea I'm not about to go down that rabbit hole.
How is that? I have installed and used many different BSD on X86, Alpha and PowerPC systems. Almost every time things have just worked...

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

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 8:08 am

jalih,
How is that?
I don't recall exactly now. The last time I tried was two or three years ago.

You know, download image, burn CD/DVD, boot machine from it, it does not work, give up and get back to work...

I did think to try again very recently when I watched Bryan Cantrill talking about ZFS and dtrace. Too busy with other things just now though.
Memory in C++ is a leaky abstraction .

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

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 8:23 am

If we count the lines of code in your complete solution, SB and C, as one must, I make it 95 lines in exface.c and extami.sb. Not including comments and blank lines.

Meanwhile the Rust solution, rustami.rs, is only 37.

When you say "add up the include lines" do you mean the actual "#include..." lines in the sources or do you mean transitively all the lines that are included from those files?

If the former, they are counted in my estimate above. Rust has none.

If the later, Rust has precisely zero. Whereas there must by thousands of lines pulled in by the headers in by exface.c

As for readability and ease of use I'm going to stick my neck out and say that it's most probably true that using one language to solve a problem is a lot easier than having to use two.
Memory in C++ is a leaky abstraction .

User avatar
bensimmo
Posts: 4187
Joined: Sun Dec 28, 2014 3:02 pm
Location: East Yorkshire

Re: Liberation through Computer Literacy

Mon Nov 18, 2019 1:09 pm

ejolson wrote:
Sun Nov 17, 2019 4:20 pm
...
I asked the former vice-president of testing whether this seemed reasonable from an educational point of view. With a whine the dog developer responded, I've been trying to do that all day. How do you combine Scratch and Python together in the same project?
It may not have a happy outcome
https://www.dailymail.co.uk/news/articl ... t-cat.html

(Warning it is a daily mail website so prepare to be bombarded by junk, get an add blocker, I believe the article is true, but it is the Daily Mail).

Return to “General programming discussion”