NXC: large bit array (Gimmick)

[HaWe]

hi,
it's about a Gimmick actually with no practical use at all:
I am curious about a large bit array datatype or work-around for this.

IIRC we once had this topic already (the search function had - again - no hits) - and the former answer was "no, not possible".

Nevertheless, the challenge is about a mathematical algorithm to find prime numbers and has been started by a member of our German Mindstorms forum;
the following approach is called "Sieve of Eratosthenes".

This algorithm needs a large array to sort out all multiples of already detected primes, but the poor memory of the NXT lets one only calculate primes up to about 32200 when using arrays of char:

Code: Select all

// Primzahlen mit Sieb des Eratosthenes

#define test 32200

#define clock() ( CurrentTick()-FirstTick() )

char list[test];


task main() {
   unsigned int i, j, hits=0;

   ClearScreen();
   SetSleepTimeout(0);

   TextOut(0,56,"Primzahlen bis:");
   for(i=2;i<test;i++)  {
      if(list[i]!=1) {
         NumOut(0, 48,i);
         ++hits;
         for(j=i*i;j<test;j+=i)  {
            list[j]=1;
         }
      }
   }
   TextOut(0,36,"fertig! gefunden:");
   NumOut (0,30, hits);
   TextOut(0,16,"Laufzeit (ms):");
   NumOut (0, 8, clock());

   while(1);
} 

Now it was made ​​the claim by another author (Linus aka linusa) that it should be possible to use bit arrays instead of char arrays in NXC.

I personally doubted that because it once already had been negated - but maybe one or the other member meanwhile found a way?
For this algorithm above every single bit in this list (or array) must be accessable (read/write) by indices and counting through indices.
If it should be possible (of course, within a reasonable time and performance), then the range of tested primes might be enlarged from about 32,000 to maybe 8 million or so ....

As I already wrote, it's only a gimmick and it is really not of great importance but I am curious anyway.

[mcsummation]

The code to do what you want is fairly simple. The problem is that the performance, running on anything other than the native hardware (not the Lego VM), will be quite poor compared to using a byte array. My guess is that it will take about 10 times as long.

[HaWe]

which code?

[mcsummation]

The code to do the bit-array.

[HaWe]

well, that was my question - but I asked for the code
we may test the performance afterwards just including it into the Eratosthenes algorithm!!

[spillerrec]

If you don't know how to do it, you should learn it as it is a treated as a basic C skill. Look up bit manipulation. Since I think you will be better off learning it yourself, I will not write the code for you.
As for the speed, it really depends on what you want to do, the usual speed vs. memory usage. (It will be quite a bit slower though.) But I certainly wouldn't test it by using it in a random algorithm. The read and write access will have different characteristics and you wouldn't be able to difference between them when testing with an algorithm like that.

btw, what was the idea with using a NXT to find primes? If you needed the primes for another algorithm, wouldn't it be better to calculate this on the computer and store the list as a file on the NXT?

[HaWe]

I don't ask for the skill - I asked if there already is a code.
I think it's rather unpolite if anyone asks for a code to reply "do it by your own, I will not write the code for you!" - if you don't want to help then better post nothing.
BTW, I don't need primes, it's just someone's challenge or gimmick.

edit:
As I just found out it won't be possible at all to have a bit array for several millions of bits for the algorithm - I guess it will be only possible to have about 240,000 as upper limit for the largest prime (CMIIW), but that's still far too low compared to other algorithms we already have (which work slower but limited only to MAX_UNSIGNED_LONG ~ 4294967295).

[spillerrec]

What mcsummation said that the code to do it would be fairly simple, not that it existed nor that he wanted to write it.
If you really want some code, here is some:

Code: Select all

byte arr[ 20000 ];
void setbitarr( unsigned long idx, bool value ){
  unsigned int index = idx / 8;
  byte mask = 1 << (idx % 8);
  arr[ index ] = ( value ) ? arr[ index ] | mask : arr[ index ] & ~mask;
}
bool readbitarr( unsigned long idx ){
  return arr[ idx / 8 ] & ( 1 << (idx % 8) );
}

Took me 5 minutes to write, didn't check it and most likely isn't perfect. But it is something like that you need to do. If you want to work with bit arrays and you want it to be efficient, you are probably better off writing it directly into your code anyway.

If you don't know how that code works, google "bit manipulation", there are plenty of good articles about it. Most APIs in C (and NXC too) uses bit manipulation somewhere, so I recommend you to learn it.

And yeah, a bit array will only give you 8 times more, so that is far from 8 million. If that was your goal, this is not the silver bullet.

[HaWe]

thank you for your efforts!
this sort of bit masks and bit shifting is really not my playing ground...

Indeed primes as large as several millions have been the goal, but anyway, I included your code into the prime sieve (searching all primes up to 32000).

The performance is as bad as it was feared (runtime more than 6 times as long as before and even almost 2x as long as a competitive algorithm checking all by "modulus"),
and most of the results are wrong ( "primes" found: 27999 instead of 2946), so your code still appears to be bugged (not surprising considering the short development time).

But nevertheless it's not bad for 5 minutes coding and it's a (too) slow but funny gimmick anyway.

Code: Select all

// Primzahlen mit Sieb des Eratosthenes
// "faked" bit array
// still bugged

#define test 32000

#define clock() ( CurrentTick()-FirstTick() )

byte arr[ test ];

void setbitarr( unsigned long idx, bool value ){
  unsigned int index = idx / 8;
  byte mask = 1 << (idx % 8);
  arr[ index ] = ( value ) ? arr[ index ] | mask : arr[ index ] & ~mask;
}

bool readbitarr( unsigned long idx ){
  return arr[ idx / 8 ] & ( 1 << (idx % 8) );
}


task main() {
   unsigned int i, j, hits=0;

   ClearScreen();
   SetSleepTimeout(0);

   TextOut(0,56,"Primzahlen bis:");
   for(i=2; i<test; i++)  {
      if(readbitarr(i)!=1) {
         NumOut(0, 48, i);
         ++hits;
         for(j=i*i; j<test; j+=i)  {
            setbitarr(j,1);
         }
      }
   }
   TextOut(0,36,"fertig! gefunden:");
   NumOut (0,30, hits);
   TextOut(0,16,"Laufzeit (ms):");
   NumOut (0, 8, clock());

   while(1);
}

[linusa]

There are possible performance improvements with this setbitarr and readbitarr code:

1.) Shift operations are slow in NXC (if anybody is interested, have a look at my NXC profiler and try for yourself, the results should be around here somewhere (or on nxtasy :/) ). You can pre-calc the 8 possible bitmasks:

Code: Select all

  byte mask[0]  = 1;
  byte mask[1]  = 2;
  byte mask[2]  = 4;
  byte mask[3]  = 8;
  byte mask[4]  = 16;
  //...

Code: Select all

  // this:
  byte mask = 1 << (idx % 8);
  // then becomes:
  mask[idx % 8];
  // use in both functions, of course!

You should also pre-calc ~mask to avoid the not-op.

Since array-lookups are (fairly) slow in NXC, you could try using a big SWITCH and see how fast it gets.

2.) In general, compiler like "const" keywords. Sophisticated compilers (gcc, MS VisualC++) will probably recognize many situations where you don't use "const" but don't modify the value, but it can't help to use it as much as possible in NXC, as it's probably not as optimizing as other compilers (just a guess).
Also, inlining the bittarr functions seems reasonable!

3.) Consider splitting the functions to setbitarrtrue, setbitarrfalse, and togglebitarr (with its own binary op). Then you save the if (?-op) and make the function smaller, if you know what you want to set (in Erasthothenes Sieve, you probably always want to set to true/false inside the loop).

4.) Try reducing calls to the bitarr functions and/or caching values...