Author: Gerd Isenberg
Date: 06:44:00 07/08/03
Go up one level in this thread
On July 08, 2003 at 08:16:01, Tim Foden wrote:
>On July 08, 2003 at 05:31:04, Gerd Isenberg wrote:
>
>>Andrew's one - as expected faster than Tim's approach
>>
>>so far:
>>Andrew n = 1799993753, time = 5.828
>>Tim n = 1799993753, time = 6.875
>>Switch256 n = 1799993753, time = 2.671
>>
>>so now i really have to work ;-)
>
>Ah... But what about with a data set where on average only 1.27405 bits are set
>(see http://www.talkchess.com/forums/1/message.html?305213)? I guess this may
>bring the numbers closer together... but my simple approach will probably still
>be slower. :)
>
>Cheers, Tim.
Hi Tim, yes you are completely right...
most often two bit set:
Andrew n = 467580016, time = 4.359
Tim n = 467580016, time = 3.672
switch n = 467580016, time = 3.156
only one bit set:
Andrew n = 450000731, time = 3.796
Tim n = 450000731, time = 3.219
switch n = 450000731, time = 2.766
Cheers,
Gerd
the listing so far:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_ITERATIONS 100000000
unsigned long n,n1,n2,n3,n4,n5,n6,n7,n8;
// Just some functions to call
void func0 () { n1 += 1; }
void func1 () { n2 += 2; }
void func2 () { n3 += 3; }
void func3 () { n4 += 4; }
void func4 () { n5 += 5; }
void func5 () { n6 += 6; }
void func6 () { n7 += 7; }
void func7 () { n8 += 8; }
int smallestpower[256] = {
-1, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
};
// one or two bits set
unsigned long randbits()
{
int rnd = rand();
// return (1<<(rnd&7));
return (1<<(rnd&7)) + ((1<<(rnd>>8)&7));
}
void tim_func ()
{
int i;
clock_t start, stop;
srand(0);
n = n1 = n2 = n3 = n4 = n5 = n6 = n7 = n8 = 0;
start = clock();
for (i = 0 ; i < MAX_ITERATIONS; i++)
{
unsigned long bits = randbits();
while (bits)
{
int bit = smallestpower[bits];
switch (bit)
{
case 0: func0(); break;
case 1: func1(); break;
case 2: func2(); break;
case 3: func3(); break;
case 4: func4(); break;
case 5: func5(); break;
case 6: func6(); break;
case 7: func7(); break;
}
bits ^= (1 << bit);
}
}
stop = clock();
n = n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8;
printf(" Tim n = %u, time = %.3f\n", n, (float)(stop - start) /
CLOCKS_PER_SEC);
}
void andrew_func ()
{
int i;
clock_t start, stop;
srand(0);
n = n1 = n2 = n3 = n4 = n5 = n6 = n7 = n8 = 0;
start = clock();
for (i = 0; i < MAX_ITERATIONS; i++)
{
unsigned long bits = randbits();
if ( bits & 0xc0 )
{
if ( bits & 0x80 ) func7();
if ( bits & 0x40 ) func6();
if ((bits &~0xc0) == 0 ) goto done;
}
if ( bits & 0x30 )
{
if ( bits & 0x20 ) func5();
if ( bits & 0x10 ) func4();
if ((bits &~0x30) == 0 ) goto done;
}
if ( bits & 0x0c )
{
if ( bits & 0x08 ) func3();
if ( bits & 0x04 ) func2();
}
if ( bits & 0x03 )
{
if ( bits & 0x02 ) func1();
if ( bits & 0x01 ) func0();
}
done:;
}
stop = clock();
n = n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8;
printf("Andrew n = %u, time = %.3f\n", n, (float)(stop - start) /
CLOCKS_PER_SEC);
}
void switch256_func ()
{
int i;
clock_t start, stop;
srand(0);
n = n1 = n2 = n3 = n4 = n5 = n6 = n7 = n8 = 0;
start = clock();
for (i = 0; i < MAX_ITERATIONS; i++)
{
unsigned long bits = randbits();
switch (bits)
{
case 0x00:
break;
case 0x01:
func0();
break;
case 0x02:
func1();
break;
case 0x03:
func0();
func1();
break;
case 0x04:
func2();
break;
case 0x05:
func0();
func2();
break;
case 0x06:
func1();
func2();
break;
case 0x07:
func0();
func1();
func2();
break;
case 0x08:
func3();
break;
case 0x09:
func0();
func3();
break;
case 0x0a:
func1();
func3();
break;
case 0x0b:
func0();
func1();
func3();
break;
case 0x0c:
func2();
func3();
break;
case 0x0d:
func0();
func2();
func3();
break;
case 0x0e:
func1();
func2();
func3();
break;
case 0x0f:
func0();
func1();
func2();
func3();
break;
case 0x10:
func4();
break;
case 0x11:
func0();
func4();
break;
case 0x12:
func1();
func4();
break;
case 0x13:
func0();
func1();
func4();
break;
case 0x14:
func2();
func4();
break;
case 0x15:
func0();
func2();
func4();
break;
case 0x16:
func1();
func2();
func4();
break;
case 0x17:
func0();
func1();
func2();
func4();
break;
case 0x18:
func3();
func4();
break;
case 0x19:
func0();
func3();
func4();
break;
case 0x1a:
func1();
func3();
func4();
break;
case 0x1b:
func0();
func1();
func3();
func4();
break;
case 0x1c:
func2();
func3();
func4();
break;
case 0x1d:
func0();
func2();
func3();
func4();
break;
case 0x1e:
func1();
func2();
func3();
func4();
break;
case 0x1f:
func0();
func1();
func2();
func3();
func4();
break;
case 0x20:
func5();
break;
case 0x21:
func0();
func5();
break;
case 0x22:
func1();
func5();
break;
case 0x23:
func0();
func1();
func5();
break;
case 0x24:
func2();
func5();
break;
case 0x25:
func0();
func2();
func5();
break;
case 0x26:
func1();
func2();
func5();
break;
case 0x27:
func0();
func1();
func2();
func5();
break;
case 0x28:
func3();
func5();
break;
case 0x29:
func0();
func3();
func5();
break;
case 0x2a:
func1();
func3();
func5();
break;
case 0x2b:
func0();
func1();
func3();
func5();
break;
case 0x2c:
func2();
func3();
func5();
break;
case 0x2d:
func0();
func2();
func3();
func5();
break;
case 0x2e:
func1();
func2();
func3();
func5();
break;
case 0x2f:
func0();
func1();
func2();
func3();
func5();
break;
case 0x30:
func4();
func5();
break;
case 0x31:
func0();
func4();
func5();
break;
case 0x32:
func1();
func4();
func5();
break;
case 0x33:
func0();
func1();
func4();
func5();
break;
case 0x34:
func2();
func4();
func5();
break;
case 0x35:
func0();
func2();
func4();
func5();
break;
case 0x36:
func1();
func2();
func4();
func5();
break;
case 0x37:
func0();
func1();
func2();
func4();
func5();
break;
case 0x38:
func3();
func4();
func5();
break;
case 0x39:
func0();
func3();
func4();
func5();
break;
case 0x3a:
func1();
func3();
func4();
func5();
break;
case 0x3b:
func0();
func1();
func3();
func4();
func5();
break;
case 0x3c:
func2();
func3();
func4();
func5();
break;
case 0x3d:
func0();
func2();
func3();
func4();
func5();
break;
case 0x3e:
func1();
func2();
func3();
func4();
func5();
break;
case 0x3f:
func0();
func1();
func2();
func3();
func4();
func5();
break;
case 0x40:
func6();
break;
case 0x41:
func0();
func6();
break;
case 0x42:
func1();
func6();
break;
case 0x43:
func0();
func1();
func6();
break;
case 0x44:
func2();
func6();
break;
case 0x45:
func0();
func2();
func6();
break;
case 0x46:
func1();
func2();
func6();
break;
case 0x47:
func0();
func1();
func2();
func6();
break;
case 0x48:
func3();
func6();
break;
case 0x49:
func0();
func3();
func6();
break;
case 0x4a:
func1();
func3();
func6();
break;
case 0x4b:
func0();
func1();
func3();
func6();
break;
case 0x4c:
func2();
func3();
func6();
break;
case 0x4d:
func0();
func2();
func3();
func6();
break;
case 0x4e:
func1();
func2();
func3();
func6();
break;
case 0x4f:
func0();
func1();
func2();
func3();
func6();
break;
case 0x50:
func4();
func6();
break;
case 0x51:
func0();
func4();
func6();
break;
case 0x52:
func1();
func4();
func6();
break;
case 0x53:
func0();
func1();
func4();
func6();
break;
case 0x54:
func2();
func4();
func6();
break;
case 0x55:
func0();
func2();
func4();
func6();
break;
case 0x56:
func1();
func2();
func4();
func6();
break;
case 0x57:
func0();
func1();
func2();
func4();
func6();
break;
case 0x58:
func3();
func4();
func6();
break;
case 0x59:
func0();
func3();
func4();
func6();
break;
case 0x5a:
func1();
func3();
func4();
func6();
break;
case 0x5b:
func0();
func1();
func3();
func4();
func6();
break;
case 0x5c:
func2();
func3();
func4();
func6();
break;
case 0x5d:
func0();
func2();
func3();
func4();
func6();
break;
case 0x5e:
func1();
func2();
func3();
func4();
func6();
break;
case 0x5f:
func0();
func1();
func2();
func3();
func4();
func6();
break;
case 0x60:
func5();
func6();
break;
case 0x61:
func0();
func5();
func6();
break;
case 0x62:
func1();
func5();
func6();
break;
case 0x63:
func0();
func1();
func5();
func6();
break;
case 0x64:
func2();
func5();
func6();
break;
case 0x65:
func0();
func2();
func5();
func6();
break;
case 0x66:
func1();
func2();
func5();
func6();
break;
case 0x67:
func0();
func1();
func2();
func5();
func6();
break;
case 0x68:
func3();
func5();
func6();
break;
case 0x69:
func0();
func3();
func5();
func6();
break;
case 0x6a:
func1();
func3();
func5();
func6();
break;
case 0x6b:
func0();
func1();
func3();
func5();
func6();
break;
case 0x6c:
func2();
func3();
func5();
func6();
break;
case 0x6d:
func0();
func2();
func3();
func5();
func6();
break;
case 0x6e:
func1();
func2();
func3();
func5();
func6();
break;
case 0x6f:
func0();
func1();
func2();
func3();
func5();
func6();
break;
case 0x70:
func4();
func5();
func6();
break;
case 0x71:
func0();
func4();
func5();
func6();
break;
case 0x72:
func1();
func4();
func5();
func6();
break;
case 0x73:
func0();
func1();
func4();
func5();
func6();
break;
case 0x74:
func2();
func4();
func5();
func6();
break;
case 0x75:
func0();
func2();
func4();
func5();
func6();
break;
case 0x76:
func1();
func2();
func4();
func5();
func6();
break;
case 0x77:
func0();
func1();
func2();
func4();
func5();
func6();
break;
case 0x78:
func3();
func4();
func5();
func6();
break;
case 0x79:
func0();
func3();
func4();
func5();
func6();
break;
case 0x7a:
func1();
func3();
func4();
func5();
func6();
break;
case 0x7b:
func0();
func1();
func3();
func4();
func5();
func6();
break;
case 0x7c:
func2();
func3();
func4();
func5();
func6();
break;
case 0x7d:
func0();
func2();
func3();
func4();
func5();
func6();
break;
case 0x7e:
func1();
func2();
func3();
func4();
func5();
func6();
break;
case 0x7f:
func0();
func1();
func2();
func3();
func4();
func5();
func6();
break;
case 0x80:
func7();
break;
case 0x81:
func0();
func7();
break;
case 0x82:
func1();
func7();
break;
case 0x83:
func0();
func1();
func7();
break;
case 0x84:
func2();
func7();
break;
case 0x85:
func0();
func2();
func7();
break;
case 0x86:
func1();
func2();
func7();
break;
case 0x87:
func0();
func1();
func2();
func7();
break;
case 0x88:
func3();
func7();
break;
case 0x89:
func0();
func3();
func7();
break;
case 0x8a:
func1();
func3();
func7();
break;
case 0x8b:
func0();
func1();
func3();
func7();
break;
case 0x8c:
func2();
func3();
func7();
break;
case 0x8d:
func0();
func2();
func3();
func7();
break;
case 0x8e:
func1();
func2();
func3();
func7();
break;
case 0x8f:
func0();
func1();
func2();
func3();
func7();
break;
case 0x90:
func4();
func7();
break;
case 0x91:
func0();
func4();
func7();
break;
case 0x92:
func1();
func4();
func7();
break;
case 0x93:
func0();
func1();
func4();
func7();
break;
case 0x94:
func2();
func4();
func7();
break;
case 0x95:
func0();
func2();
func4();
func7();
break;
case 0x96:
func1();
func2();
func4();
func7();
break;
case 0x97:
func0();
func1();
func2();
func4();
func7();
break;
case 0x98:
func3();
func4();
func7();
break;
case 0x99:
func0();
func3();
func4();
func7();
break;
case 0x9a:
func1();
func3();
func4();
func7();
break;
case 0x9b:
func0();
func1();
func3();
func4();
func7();
break;
case 0x9c:
func2();
func3();
func4();
func7();
break;
case 0x9d:
func0();
func2();
func3();
func4();
func7();
break;
case 0x9e:
func1();
func2();
func3();
func4();
func7();
break;
case 0x9f:
func0();
func1();
func2();
func3();
func4();
func7();
break;
case 0x0a0:
func5();
func7();
break;
case 0x0a1:
func0();
func5();
func7();
break;
case 0x0a2:
func1();
func5();
func7();
break;
case 0x0a3:
func0();
func1();
func5();
func7();
break;
case 0x0a4:
func2();
func5();
func7();
break;
case 0x0a5:
func0();
func2();
func5();
func7();
break;
case 0x0a6:
func1();
func2();
func5();
func7();
break;
case 0x0a7:
func0();
func1();
func2();
func5();
func7();
break;
case 0x0a8:
func3();
func5();
func7();
break;
case 0x0a9:
func0();
func3();
func5();
func7();
break;
case 0x0aa:
func1();
func3();
func5();
func7();
break;
case 0x0ab:
func0();
func1();
func3();
func5();
func7();
break;
case 0x0ac:
func2();
func3();
func5();
func7();
break;
case 0x0ad:
func0();
func2();
func3();
func5();
func7();
break;
case 0x0ae:
func1();
func2();
func3();
func5();
func7();
break;
case 0x0af:
func0();
func1();
func2();
func3();
func5();
func7();
break;
case 0x0b0:
func4();
func5();
func7();
break;
case 0x0b1:
func0();
func4();
func5();
func7();
break;
case 0x0b2:
func1();
func4();
func5();
func7();
break;
case 0x0b3:
func0();
func1();
func4();
func5();
func7();
break;
case 0x0b4:
func2();
func4();
func5();
func7();
break;
case 0x0b5:
func0();
func2();
func4();
func5();
func7();
break;
case 0x0b6:
func1();
func2();
func4();
func5();
func7();
break;
case 0x0b7:
func0();
func1();
func2();
func4();
func5();
func7();
break;
case 0x0b8:
func3();
func4();
func5();
func7();
break;
case 0x0b9:
func0();
func3();
func4();
func5();
func7();
break;
case 0x0ba:
func1();
func3();
func4();
func5();
func7();
break;
case 0x0bb:
func0();
func1();
func3();
func4();
func5();
func7();
break;
case 0x0bc:
func2();
func3();
func4();
func5();
func7();
break;
case 0x0bd:
func0();
func2();
func3();
func4();
func5();
func7();
break;
case 0x0be:
func1();
func2();
func3();
func4();
func5();
func7();
break;
case 0x0bf:
func0();
func1();
func2();
func3();
func4();
func5();
func7();
break;
case 0x0c0:
func6();
func7();
break;
case 0x0c1:
func0();
func6();
func7();
break;
case 0x0c2:
func1();
func6();
func7();
break;
case 0x0c3:
func0();
func1();
func6();
func7();
break;
case 0x0c4:
func2();
func6();
func7();
break;
case 0x0c5:
func0();
func2();
func6();
func7();
break;
case 0x0c6:
func1();
func2();
func6();
func7();
break;
case 0x0c7:
func0();
func1();
func2();
func6();
func7();
break;
case 0x0c8:
func3();
func6();
func7();
break;
case 0x0c9:
func0();
func3();
func6();
func7();
break;
case 0x0ca:
func1();
func3();
func6();
func7();
break;
case 0x0cb:
func0();
func1();
func3();
func6();
func7();
break;
case 0x0cc:
func2();
func3();
func6();
func7();
break;
case 0x0cd:
func0();
func2();
func3();
func6();
func7();
break;
case 0x0ce:
func1();
func2();
func3();
func6();
func7();
break;
case 0x0cf:
func0();
func1();
func2();
func3();
func6();
func7();
break;
case 0x0d0:
func4();
func6();
func7();
break;
case 0x0d1:
func0();
func4();
func6();
func7();
break;
case 0x0d2:
func1();
func4();
func6();
func7();
break;
case 0x0d3:
func0();
func1();
func4();
func6();
func7();
break;
case 0x0d4:
func2();
func4();
func6();
func7();
break;
case 0x0d5:
func0();
func2();
func4();
func6();
func7();
break;
case 0x0d6:
func1();
func2();
func4();
func6();
func7();
break;
case 0x0d7:
func0();
func1();
func2();
func4();
func6();
func7();
break;
case 0x0d8:
func3();
func4();
func6();
func7();
break;
case 0x0d9:
func0();
func3();
func4();
func6();
func7();
break;
case 0x0da:
func1();
func3();
func4();
func6();
func7();
break;
case 0x0db:
func0();
func1();
func3();
func4();
func6();
func7();
break;
case 0x0dc:
func2();
func3();
func4();
func6();
func7();
break;
case 0x0dd:
func0();
func2();
func3();
func4();
func6();
func7();
break;
case 0x0de:
func1();
func2();
func3();
func4();
func6();
func7();
break;
case 0x0df:
func0();
func1();
func2();
func3();
func4();
func6();
func7();
break;
case 0x0e0:
func5();
func6();
func7();
break;
case 0x0e1:
func0();
func5();
func6();
func7();
break;
case 0x0e2:
func1();
func5();
func6();
func7();
break;
case 0x0e3:
func0();
func1();
func5();
func6();
func7();
break;
case 0x0e4:
func2();
func5();
func6();
func7();
break;
case 0x0e5:
func0();
func2();
func5();
func6();
func7();
break;
case 0x0e6:
func1();
func2();
func5();
func6();
func7();
break;
case 0x0e7:
func0();
func1();
func2();
func5();
func6();
func7();
break;
case 0x0e8:
func3();
func5();
func6();
func7();
break;
case 0x0e9:
func0();
func3();
func5();
func6();
func7();
break;
case 0x0ea:
func1();
func3();
func5();
func6();
func7();
break;
case 0x0eb:
func0();
func1();
func3();
func5();
func6();
func7();
break;
case 0x0ec:
func2();
func3();
func5();
func6();
func7();
break;
case 0x0ed:
func0();
func2();
func3();
func5();
func6();
func7();
break;
case 0x0ee:
func1();
func2();
func3();
func5();
func6();
func7();
break;
case 0x0ef:
func0();
func1();
func2();
func3();
func5();
func6();
func7();
break;
case 0x0f0:
func4();
func5();
func6();
func7();
break;
case 0x0f1:
func0();
func4();
func5();
func6();
func7();
break;
case 0x0f2:
func1();
func4();
func5();
func6();
func7();
break;
case 0x0f3:
func0();
func1();
func4();
func5();
func6();
func7();
break;
case 0x0f4:
func2();
func4();
func5();
func6();
func7();
break;
case 0x0f5:
func0();
func2();
func4();
func5();
func6();
func7();
break;
case 0x0f6:
func1();
func2();
func4();
func5();
func6();
func7();
break;
case 0x0f7:
func0();
func1();
func2();
func4();
func5();
func6();
func7();
break;
case 0x0f8:
func3();
func4();
func5();
func6();
func7();
break;
case 0x0f9:
func0();
func3();
func4();
func5();
func6();
func7();
break;
case 0x0fa:
func1();
func3();
func4();
func5();
func6();
func7();
break;
case 0x0fb:
func0();
func1();
func3();
func4();
func5();
func6();
func7();
break;
case 0x0fc:
func2();
func3();
func4();
func5();
func6();
func7();
break;
case 0x0fd:
func0();
func2();
func3();
func4();
func5();
func6();
func7();
break;
case 0x0fe:
func1();
func2();
func3();
func4();
func5();
func6();
func7();
break;
case 0x0ff:
func0();
func1();
func2();
func3();
func4();
func5();
func6();
func7();
break;
}
}
stop = clock();
n = n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8;
printf("switch n = %u, time = %.3f\n", n, (float)(stop - start) /
CLOCKS_PER_SEC);
}
void main (void)
{
andrew_func();
tim_func ();
switch256_func ();
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.