Peijen's Programming Thread 1.0

Posts you want to find years later go here.
Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Log of 2

Post by Peijen »

is there a easy way to deteremine the log of 2 without using the log function?

let's say i have the following

Code: Select all

enum shit {
  black = 1,
  brown = 2,
  yellow = 4,
  green = 8,
  red = 16
};

unsigned char *tag;
I want tag[0] to be associated to black, tag[1] to brown and so on. What's the fastest way of deremining log of 2 without a look up table?

Jason
Veteran Doodler
Posts: 1520
Joined: Fri Jul 18, 2003 12:53 am
Location: Fairfax, VA

Post by Jason »

and with a bit mask and then check for true or false.

Jonathan
Grand Pooh-Bah
Posts: 6722
Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:

Post by Jonathan »

Use less memory with an unsigned int instead of a char *.

Code: Select all

const unsigned int black = 1;
const unsigned int brown = 2;
const unsigned int yellow = 4;
const unsigned int green = 8;
const unsigned int red = 16;

unsigned int tag;
tag = dostuff();
if (tag & black) cout << "tag is black\n";

Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Post by Peijen »

Dwindlehop wrote:Use less memory with an unsigned int instead of a char *.
it's not really a char*, it's actually char [log2(ubound)+1].

Here is how I want to use this.

Code: Select all

enum shit {
  black = 1, 
  brown = 2, 
  yellow = 4, 
  green = 8, 
  red = 16 
}; 

unsigned char tag[5];

shit a;

void addshit(shit s, char t) {
  a &= s;
  if (s & black) {
    tag[0] = t;
  } // etc
}

char shitwhat(shit s) {
  if (a & s) {
    switch (s) {
    case black:
      return tag[0];
    // etc
    }
  }
}
I am will aware of bit mask and stuff, it's extra information associated with each flag that I am interest in.
Last edited by Peijen on Tue Aug 12, 2003 5:10 pm, edited 1 time in total.

Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Post by Peijen »

oops should finish typing before hit submit.

What I wanted is less if/swtich statment so the code would look like this

Code: Select all

void addshit(shit s, char t) {
  a &= s;
  tag[log(s)] = t;
}

char shitwhat(shit s) {
if (a & s) return tag[log(s)];
}
This way I can add new element to enum without adding extra code to handle each of them. However I don't want to use the <math.h>'s log function since it's probably slower and more complex than what I needed.
Last edited by Peijen on Tue Aug 12, 2003 5:13 pm, edited 1 time in total.

Jonathan
Grand Pooh-Bah
Posts: 6722
Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:

Post by Jonathan »

Use an STL map? Because that's what this really is, is a hash.

Jonathan
Grand Pooh-Bah
Posts: 6722
Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:

Post by Jonathan »

The answer, of course, is a recursive function that shifts bits until it sees a one. The race to write it starts... NOW!

Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Post by Peijen »

Dwindlehop wrote:Use an STL map? Because that's what this really is, is a hash.
well memory size and all that, but you are probably right. Why write your own code when others already did it ...

Jonathan
Grand Pooh-Bah
Posts: 6722
Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:

Post by Jonathan »

Code: Select all

int log2(int a) {
  // base case
  if(a == 1) 
     return 0;
  else
     return 1+log2(a>>1);
}
This only works for powers of two. But that's what you asked for.

Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Post by Peijen »

Dwindlehop wrote:The answer, of course, is a recursive function that shifts bits until it sees a one. The race to write it starts... NOW!
What this is what I don't want to do ...

long index(unsigned long x)
{
long j = 1;
for (int i = 0; i < -1; ++i) {
if ((j<<i) == x) return i;
}
}

Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Post by Peijen »

damn you for posting before I do, but my solution is better anyway ...

Jonathan
Grand Pooh-Bah
Posts: 6722
Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:

Post by Jonathan »

Peijen wrote:damn you for posting before I do, but my solution is better anyway ...
you, sir, have no functional programming soul.

Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Post by Peijen »

Dwindlehop wrote:
Peijen wrote:damn you for posting before I do, but my solution is better anyway ...
you, sir, have no functional programming soul.
What I ask for is speed, and less memory print. recursive function is alot worse than lookup table.

quantus
Tenth Dan Procrastinator
Posts: 4891
Joined: Fri Jul 18, 2003 3:09 am
Location: San Jose, CA

Post by quantus »

Is this really going to be the inside of a tight loop where you really require speed? The sheer fact that you're resisting a hash (array in this case) is absurd if you really really want speed. It's the only thing where pointer arithmetic is quick and simple. Hint, to truly make this fast, make sure your compiler is aligning the array with the cache line. Anyways, you took 213, you know this shit.

Peijen
Minion to the Exalted Pooh-Bah
Posts: 2790
Joined: Fri Jul 18, 2003 2:28 pm
Location: Irvine, CA

Post by Peijen »

quantus wrote:Is this really going to be the inside of a tight loop where you really require speed?
tell you the truth, not really. I have pretty much optimized all formular used in the program. The most of the time will be spend reading/writing data.
quantus wrote:The sheer fact that you're resisting a hash (array in this case) is absurd if you really really want speed. It's the only thing where pointer arithmetic is quick and simple. Hint, to truly make this fast, make sure your compiler is aligning the array with the cache line. Anyways, you took 213, you know this shit.
I am compareing my solution to Jon's. At this point I don't really care about cache performance, since I have no idea what kind of computer (processor) the broker is using, and I am not about to look up if there is difference between 486/P/Pii/Piii/Piv/Duran/Thunderbird/etc.

VLSmooth
Tenth Dan Procrastinator
Posts: 3055
Joined: Fri Jul 18, 2003 3:02 am
Location: Varies
Contact:

Post by VLSmooth »

quantus wrote:Anyways, you took 213, you know this shit.
Since you're talking about coursework, you KNOW you want to take 212 now. You'll love/hate it. Well, you'll at least hate it :)

quantus
Tenth Dan Procrastinator
Posts: 4891
Joined: Fri Jul 18, 2003 3:09 am
Location: San Jose, CA

Post by quantus »

courses? what are those?

Jonathan
Grand Pooh-Bah
Posts: 6722
Joined: Tue Sep 19, 2006 8:45 pm
Location: Portland, OR
Contact:

Post by Jonathan »

quantus wrote:courses? what are those?
you don't have any left?

Jason
Veteran Doodler
Posts: 1520
Joined: Fri Jul 18, 2003 12:53 am
Location: Fairfax, VA

Post by Jason »

Dwindlehop wrote:
quantus wrote:courses? what are those?
you don't have any left?
maybe that's why he keeps failing his PhD qualifier.

quantus
Tenth Dan Procrastinator
Posts: 4891
Joined: Fri Jul 18, 2003 3:09 am
Location: San Jose, CA

Post by quantus »

I haven't really had classes since Fall last year when I took one because I felt like it.

Post Reply