On 11/14/07, Chris Fant <[EMAIL PROTECTED]> wrote:
> Based on more recent emails, this may not be useful anymore, but I
> have a list of 361 32-bit numbers that satisfy these properties in
> case anyone is interested.
I'd be interested in your implementation tricks. Where did the number
17 come from?
Other stuff...
John and Jason's optimization suggestions are both good, but they
point in different directions. (Of course, John had a complete
solution to begin with.) I have a 64-bit machine, and in that case I
think that the bitmask approach, with Jason's addition, is the clear
choice, creating some pretty tight code:
/** @return true iff the input value is either zero or the sum of
at most mMaxRepetitions of a single code() value. */
bool operator()(uint64_t codeSum) const {
return codeSum < mThreshold && !((codeSum/(codeSum/mDivisor)) & mMask);
}
I wrote a class for this that, for lack of a less ugly solution (I
need to get some more web page space), I have appended to this email.
There are three files -- a .cpp file, a .hpp file, and another .cpp
file just for testing and illustrating how to use it. It could use
more thorough tests and more comments, and the class name is lame, but
hopefully it works.
#ifndef _IsOneSum_hpp
#define _IsOneSum_hpp
#include <stdint.h>
#include <vector>
// Based on ideas of John Tromp, Jason House, and me (Eric Boesch).
class IsOneSum {
public:
/** @param codeCnt: all inputs to the code() method must be
strictly less than this value.
@param maxRepetitions: create codes that can be used to detect
up to maxRepetitions repetitions of the same value. Larger
numbers of repetitions will not be distinguishable from sums
of multiple different code values. */
IsOneSum(int codeCnt, int maxRepetitions);
/** @return true iff the input value is either zero or the sum of
at most mMaxRepetitions of a single code() value. */
bool operator()(uint64_t codeSum) const {
return codeSum < mThreshold && !((codeSum/(codeSum/mDivisor)) & mMask);
}
/** @return the code corresponding to the input value i. */
uint64_t code(int i) const {
return mCodes[i];
}
protected:
int const mCodeCnt;
int const mMaxRepetitions;
// These values should be constant too.
uint64_t mThreshold;
uint64_t mDivisor;
uint64_t mMask;
std::vector<uint64_t> mCodes;
};
#endif
----
// IsOneSum.cpp
#include "IsOneSum.hpp"
IsOneSum::IsOneSum(int iCodeCnt, int iMaxRepetitions)
: mCodeCnt(iCodeCnt), mMaxRepetitions(iMaxRepetitions),
mCodes(iCodeCnt) {
// Let codeBit equal the least power of two exceeding
// mMaxRepetitions.
int codeBitsPerBit = 0;
int codeBit;
for (codeBit = 1;
codeBit <= mMaxRepetitions;
codeBit<<=1, ++codeBitsPerBit)
; // do nothing
// Per Jason House's suggestion, this bottom part of the mask
// obviates the (codeSum % (codeSum/mDivisor)) == 0 test.
mMask = codeBit - 1;
for (int bit = 1;
bit < mCodeCnt;
bit<<=1, codeBit<<=codeBitsPerBit) {
// This part of the mask verifies that this
// base-(1<<codeBitsPerBit) digit of the quotient (codeSum /
// (codeSum/mDivisor)) equals 0 or 1.
mMask |= ((1 << codeBitsPerBit) - 2) * codeBit;
for (int i = 1; i < mCodeCnt; ++i) {
if (i & bit) {
mCodes[i] += codeBit;
}
}
}
mDivisor = codeBit;
for (int i = 0; i < mCodeCnt; ++i) {
mCodes[i] += mDivisor;
}
mThreshold = (mMaxRepetitions + 1) * mDivisor;
}
------
// IsOneSumTest.cpp
#include <iostream>
#include <iomanip>
#include <stdint.h>
#include "IsOneSum.hpp"
using namespace std;
int main(int argc, char**argv) {
IsOneSum is1(361, 4);
cout << hex;
for (int i = 0; i < 20; ++i) {
cout << i << " -> " << is1.code(i) << endl;
}
cout << 360 << " -> " << is1.code(360) << endl;
uint64_t sum;
sum = is1.code(1) + is1.code(2) + is1.code(3);
cout << "1,2,3 -> " << sum << " : " << is1(sum) << endl;
sum = is1.code(360) + is1.code(360) + is1.code(360);
cout << "360,360,360 -> " << sum << " : " << is1(sum) << endl;
sum += is1.code(360);
cout << "360,360,360,360 -> " << sum << " : " << is1(sum) << endl;
sum = is1.code(0) + is1.code(0) + is1.code(0) + is1.code(0) + is1.code(0);
cout << "0,0,0,0,0 -> " << sum << " : " << is1(sum) << endl;
}
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
