Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Interesting numbers about hashing - 32 bits are clearly not enough

Author: Miguel A. Ballicora

Date: 09:20:56 12/07/01

Go up one level in this thread


On December 07, 2001 at 11:38:17, Dieter Buerssner wrote:

>On December 07, 2001 at 10:44:43, Miguel A. Ballicora wrote:
>
>>On December 07, 2001 at 09:00:27, Uri Blass wrote:
>>
>>>I did not understand exactly what you do
>>>
>>>1)My program does not understand the meaning of long long
>>>
>>>I get error C2632: 'long' followed by 'long' is illegal
>>>I guess that you probably mean __int64 so I cahnged every long long to __int64
>>
>>No, I meant long long because that's part of the dialect of GCC, which is
>>the one that Bob uses more often, I guess, since he says that develops in linux.
>>They are suppose to mean the same.
>
>Just to add a bit. long long and unsigned long long are not a dialect anymore.
>They are part of the official ISO C99 Standard. The format specifiers for
>printing are %lld and %llu. I guess, sooner or later, all the major compilers
>should support [unsigned] long long.
>
>>typedef __int64 UI64;  /* long long for GCC */
>>char *
>>int64tostring (UI64 x, char *s)
>>{
>>  enum { GIGA = 1000000000
>>  };
>>  unsigned int a = (unsigned int)(x/GIGA);
>>  unsigned int b = (unsigned int)(x%GIGA);
>>  if (x>GIGA)
>>     sprintf(s,"%d%d",a,b);
>>  else
>>     sprintf(s,"%d",b);        /* this solves the problem of the 0 in front */
>>  return s;
>>}
>
>For printing unsigned int, the format specifier %d is not correct (although it
>will probably work).

Thanks Dieter.
you code is better, to fit my previous code (I used unsigned). However, "%d"
will work too. Note that the number will be always less than a giga so it will
always fit in a int32. I am making a lot of assumptions here that make nervous,
like int is 32 bits. However, we are starting with an assumption that is
not standard from the beginning like there is an int64 type.

>
>  if (x >= GIGA) /* Note the >=; I would use a > 0 */
>     sprintf(s,"%u%09u",a,b);
>  else
>     sprintf(s,"%u",b);

That's better, it takes into account Sune's concern with the padding.
That is the beauty of sprintf, it is very powerful. But the user (me) forgets
to use all the flags :-)
I agree >= should be used and now it should work. The useful range of this
code is not 64 bits (1 GIGA, is not 2^32) but close enough: 2^32 * 10^9
which is ok for at least 61 bits, which is more than we can even dream to
analyze in years.

>
>As your code, also my snippet is untested.
>
>BTW. All this printing is also the reason, that I did not convert to 64 bit
>counters, and not the totally insignificant runtime overhead. The typedef is no

If I use bigger counters, I might try something more portable like keeping
track of the number in two unsigned long ints. Since nodes advance one by one
in their most time consuming operation, the overhead of adding 1 should be
minimal (just a guess). I do not even need to use "if"'s.

Regards,
Miguel



>problem, but printing is done at various places. Eugenes solution is also not
>unproblematic, because it makes all those strings longer than my screen width
>... Also, it does by default not allow to give a specifier for the width, but
>this could be changed by only defining the "llu" part.
>
>I guess, here C++ coders have some advantage here.

>/* My coding excersize - totally untested */
>char *UI64_tostr(UI64 x, char *buf)
>{
>  char c;
>  char *bp, *sp;
>
>  bp = buf;
>
>  /* run the loop once for x=0 */
>  do
>  {
>    dig = x % 10;
>    x /= 10;
>    *bp++ = dig+'0';
>  }
>  while (x != 0);
>  *bp = '\0';
>
>  /* reverse the string */
>  sp = buf;
>  --bp; /* points to most significant digit, now */
>  while (bp > sp)
>  {
>    c = *sp;
>    *sp++ = *bp;
>    *bp-- = c;
>  }
>  return buf;
>}
>
>Regards,
>Dieter



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.