Author: Ratko V Tomic
Date: 12:34:36 11/15/99
Go up one level in this thread
> I haven't read all of your other two posts (they will take a while to > digest), but I am still confused on how you could encode/decode a 117 > bit (143 - 26 bit) single value. Seems beyond the capabilities of > normal C unless I'm missing something (a special library for large > binary values maybe). Well, you would certainly need the large integer multiply & divide operations for calculating the binomial coefficients. The multiply, add and subtract need to work in the full precision (155 bits), while the large divide occurs only in the binomial coefficients, whith small denominators (such as k!, with k<=10), hence it would be a large integer divided by a 32 bit integer at most, which is the easy and quick case of division to implement). The +,- and * are easy in any precision. For the n-digit integers (and, say, a byte or an int32 being a single "digit"), the multiply can be easily done so that the number of digit*digit multiplications is proportional to the n^1.5 instead of the n^2, which the regular paper and pencil method would use. So, yes, we don't have these data types and operations on them ready made in standard C, but we don't have Huffman coding ready made in standard C, either, or much of the rest of the data structures or operations on them in the overall algorithm (many of which are probably trickier to implement than a few large integer operations, which one can copy out of the Knuth Vol 2, or find some C library on the web). > digest), but I am still confused on how you could encode/decode a 117 > bit (143 - 26 bit) single value. Seems beyond the capabilities of The 143 bit (or rather 142 bits) for the worst case position, referes to the placement part of the code, so you wouldn't remove the 26 bits from it (for the MC26 code). Rather the MC26 code is in addition to the 142 bits, which would make the total code 142+26=168 bits, if one doesn't use the Huffman code to reduce MC26 code for these types of positions, with large number of placements for a given material. In this case the Huffman code for this MC26 state (this material content) would have the length 155-142=13 bits. In other words, the Huffman code for any of the 58 million Material Content states (for which I used MC26 code only in the intermediate phase of coding, as work variables) have the length exactly completing the placement code length for the given material to the 155 bits. The worst case, the 142 bit placement code (MP code), thus has a 13 bit Huffman code for its MC part. The "best" case, the 2 lone kings, needing only 12 whole bits for their placement code, would have their Material Content Huffman code of 155-12=143 bits, i.e. to specify that the material is 2 lone kings (or in our count records, to have all C1,..,C10 zeros) one would use a 143 bit Huffman code. But to specify the 30 piece "worst" case material counts, one would use only a 13 bit Material Count Huffman code (which happens to be half the size of the MC26 uniform code). The point of the Huffman code was to make the full (MC+MP part) position code uniform in length, exactly 155 bits for any position. That minimizes the worst case and also minimizes the average case for a random pick out of the 2.46*10^46 positions.
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.