GP2X Interesting Bit Of Logic/maths/code Needed For Binary Problem

[ledow]

Okay, I have a need for a function which does the following:

CODE
int next_binary_string_with_x_bits(int start, int x)


It takes a number (start) which has "x" 1's in it's binary expression. It then returns the next highest number which has the same property.

So:

CODE
next_binary_string_with_x_bits(0, 2) gives 3 <-- 0011 in binary, the first number after zero to have two bits set.
next_binary_string_with_x_bits(3, 2) gives 5 <-- 0101 in binary, the next number after 3 to have two bits set.
next_binary_string_with_x_bits(5, 2) gives 6 <-- 0110 in binary
next_binary_string_with_x_bits(6, 2) gives 9 <-- 1001 in binary


and

CODE
next_binary_string_with_x_bits(0, 5) gives 31 <-- 11111 in binary, the first number after 0 to have 5 bits set.
next_binary_string_with_x_bits(31, 5) gives 47 <-- 101111 in binary


Now, I've tried a few things that work but I can't seem to find a nice, fast way of doing this quickly. Even my primitive mind's recall of the maths that I've done hasn't produced anything better than the function below which would give significant speedups.

I need to be able to run this function a LOT - it's used several dozen times in an O(N) algorithm to generate a puzzle of certain sizes, but I also need to build very deep game trees of this puzzle using the same method and that means it needs to be FAST if it's to run on the GP2X. I need it to run on numbers which are mostly within the integer range (e.g. no more than 65535, usually not even more than 256). At the moment, I have something similar to:

CODE
int next_binary_string_with_x_bits(int start, int x)
{
// Start at "start", keep adding one.
for(int i=start;i<MAX_INT;i++)
// If the number of the bits is right, break early and return the number.
if(count_bits(i) == count_bits(x))
return(i)
return(-1) // Error condition for "there isn't a suitable binary string".
}



where count_bits is a very fast function for counting the number of 1's in a binary representation.

That's not exact code, just a hint of the way I'm doing it... the exact code is a lot nicer, caches certain parts, prevents overflow, limits the size of the output integer to a requested limit (e.g. 8 bits), terminates much quicker without having to iterate all the way up to MAX_INT and has other little optimisations here and there.

Count_bits functions are ten-a-penny and there's all sorts of optimisation on them that makes them incredibly fast in both plain C and machine code, which is why I'm able to use them in such a way and get results which allow me to continue coding the more interesting parts of this particular puzzle. However, this function can still take quite a while to return on 200MHz - 600MHz machines. Whereas you can get count_bits functions which return in a time proportional to the number of bits actually set, this function returns in the time it takes to count up to the next number that has x bits set (which varies enormously and can be a long time.... take, for example, the number 134217728. This has binary expression: 1000000000000000000000000000. Now say that you ask for the next number with only 1 bit set....).

I imagine that there HAS to be a quicker way of coding this function, even if it means horrible things like precomputed tables, fancy XOR'ing or something. It seems an obvious candidate for some sort of boolean operations that provide the answer extremely quickly using low-level routines, but does anyone have any idea on how to implement a nice, fast, programmatic way of generating the results needed. I can do the speedups like caching answers and so on but I still need a fast way of generating the actual data on startup with a nice fast function like the one above.

Any language will do - I can translate most things to the language of my choice. I need it to do at least integers, but the possibility of expansion is vital because these puzzles can get very silly very quickly (One example would be a 64x64 puzzle, which would require this function to operate on binary strings 127bits long with an average of 64 bits set... so you're looking at some incredibly large numbers (2^127) and HUGE gaps between answers).

Anyone fancy a bit of mind-blowing?

 

[Pickle]

I would try a pre-calculated table. Your only loss will be memory.
Worst case you have 65535 rows at 4 bytes each at 16 (bits) columns
So 65535 * 4 * 16 = 4,194,240

But you could save memory for example there's only one possibility for a number with 16 bits: 0xFFFF
For example theres only 16 possibilities for a number with 15 bits and one 1 bit.
You could create a separate array for each bit count with all the numbers of that size. It might cut down on the total numbers you would have to iterate through.

 

[Geuben]

So, heres what I've come up with. Not sure how fast this code will be though.

It works on the principle that the start number can be written in the form:

2^x + 2^y + 2^z

where x,y and z are the powers associated with the 1 bits in the start int. The above polynomial is for a int with 3 '1' bits, the polynomial will always contain the same number of terms and the number of '1' bits you are looking for.

The next number with this many '1' bits can be found by

2^x + 2^y + 2^(z+1)

if z+1 = y then y becomes y+1 and then if y+1 = x then x become x+1 etc etc etc.

using this I "think" i've come up with some code that will work. Not sure if it does work as i havent tested it and i dont know how fast it will be either but here goes.

CODE


int next_string_with_x_bits(int start,int x)
int power[maximum number of bits you will want to find ever];
int j = 1;
int output = 0;

//-------------this section determines the polynomial for the start int --------
for(i=0;i<=x;i++)
{
while(((start >> 1) % 2) == 0) // bit shifts right 1 place and checks if LSB is 1 (odd)
{j+=1; // if LSB is 0 then increase j, which keeps count of how many shifts
}
power = j; // store j count in the array for each '1' found
}
//------------------------------------------------------------------------------------
//------------this section calculates the next string with right number of '1' bits --

for(i=0;i<=x;i++)
{
if(power != (power[i+1]-1))
power +=1;
else
power[i+1] +=1;
i = x+1; // exit for loop
}
//------------------------------------------------------------------------------------
//-----------create output int -----------------------------------------------------
for(i=0;i<=x;i++)
{
output += (1 << (power)); // builds output int from 2^power
}
//--------------------
return output;




Hope that helps, if you need any more explanation then just ask.

Geuben

edit: made a change to the code
edit 2: oh wait, still not quite right, hold on.
edit 3: fixed...i think
edit 4: nah wait, it doesnt work...the section that calculates the next string isnt right....
edit 5: needs fixing
FINAL EDIT: Fixed, untested.

 

[ledow]

Thanks for the suggestions, both. I'll look into them.

The problem with Pickle's suggestion is that it doesn't scale at all well and generating those tables in the first place means either 4Mb of static stuff thrown into the executable or waiting while 4Mb of data is generated using some algorithm similar to the one I have already churns through them all and stores them. It doesn't scale well to, e.g. 64-bit strings (because then you get into combining those 16-bit strings that you pre-computed and somehow merging them based on whether the two 16-bit strings you choose have enough bits, but not too many, in total).

Geuben's suggestion is the along the lines that I was thinking of myself, but they've gone as far as to provide some code. It looks like a binary cascade, as far as I can tell from a quick glance, and I was trying to picture how such a thing would work and that's certainly an idea worth testing and extending.

It looks like execution time might depend slightly on the length of the string but it looks more feasible for large strings (e.g. I can happily replace "int" by "long long" everywhere and not worry about it blowing up). It may well be that the best suggestion is a choice of algorithm to use depending on the size of the parameters. E.g. for "x = 1", it's never anything more than a left-shift providing the start number is valid. For reasonable amounts of x in reasonably sized strings (e.g. no more than about 16 bits in total), my initial algorithm is quite fast and it may well be that for large strings, Geuben's suggestion is the best.

I'll will do a small pilot and see how they work "in real life" when it gets put through gcc and run on ARM/x86 of the 200-600MHz range.

edit: made a change to the code
edit 2: oh wait, still not quite right, hold on.
edit 3: fixed...i think
edit 4: nah wait, it doesnt work...the section that calculates the next string isnt right....
edit 5: needs fixing
FINAL EDIT: Fixed, untested.

LOL @ the above.

 

[gbouilland]

Deleted ;o)

 

[M-HT]

Here's my version of the algorithm.
Some values must be pre-calculated (preferably during or before compilation).
It contains two functions - one for 8-bit start values and one for 16-bit start values.
The function for 16-bit values uses function for 8-bit values.
This can be generalized (with a bit of work) to construct a function for (8*i)-bit values using function for (8*(i-1))-bit values.
Even better (and faster) generalization is to construct a function for 2^n-bit values using function for 2^(n/2)-bit values.

CODE

// pre-calculated number of bits for numbers in range 0-255
unsigned int count_bits8[256];

// pre-calculated values - next_value8[x, start] = next_binary_string_with_x_bits(start, x+1)
unsigned int next_value8[8][256];

// start must be in range 0-255
unsigned int next_binary_string_with_x_bits_8(unsigned int start, unsigned int x)
{
if (x == 0 || x > 32) return 0; // error value

if (x > 8)
{
return 0xffffffff >> (32 - x);
}
else
{
return next_value8[x - 1][start]; // pre-calculated value
}
}


// start must be in range 0-65535
unsigned int next_binary_string_with_x_bits_16(unsigned int start, unsigned int x)
{
unsigned int bit_count_higher_byte, higher_byte, lower_byte, iter, max_iter, min_value, value;

if (x == 0 || x > 32) return 0; // error value

if (x > 16)
{
return 0xffffffff >> (32 - x);
}

higher_byte = start >> 8;
bit_count_higher_byte = count_bits8[higher_byte];

// first possibility - higher byte stays the same
if (x > bit_count_higher_byte)
{
lower_byte = next_binary_string_with_x_bits_8(start & 0xff, x - bit_count_higher_byte);

if ( (higher_byte == 0) || (lower_byte < 256) )
{
return (higher_byte << 8) | lower_byte;
}
}

min_value = 0xffffffff;

iter = (x > 9)?(x - 8)1);
max_iter = (x < 8)?(x)8);

for (; iter <= max_iter; iter++)
{
value = (next_binary_string_with_x_bits_8(higher_byte, iter) << 8) | (0xff >> (8 - (x-iter)));

if (value < min_value) min_value = value;
}

return min_value;
}

 

[Parkydr]

Here's another solution - cycle combinations of n bits

Pros: Less values to check
Cons: recursive function calls

CODE

#include <iostream>

using namespace std;

int b(int total, int start, int l)
{
if (l < 0) return total;

int n = 1 << l;
int t = 0;
while ((total&n) == 0 && t <= start)
{
t = b(total + n, start, l-1);
n <<= 1;
}

return t;
}

int next_binary_string_with_x_bits(int start, int x)
{
return b(0, start, x-1);
}

int main (int argc, char** argv)
{
cout << next_binary_string_with_x_bits(0, 2) << endl;
cout << next_binary_string_with_x_bits(3, 2) << endl;
cout << next_binary_string_with_x_bits(5, 2) << endl;
cout << next_binary_string_with_x_bits(6, 2) << endl;

return 0;
}

 

[gbouilland]

Any language will do.

Anyone fancy a bit of mind-blowing?

CODE

$start_bin = unpack("B32", pack("N", $start)); # decimal string to binary string
$start_bin_rev = reverse($start_bin);

# replace first "10" occurence by "01" and, if necessary, move preceding concatenated "1"s before leading concatenated "0"s
$start_bin_rev =~ s/([0]*)([1])([1]*)([0])/\3\1\4\2/; # Replaced ([1]*)([1]) by ([1])([1]*) for speed efficiency
$next_bin_rev = $start_bin_rev

$next_bin = reverse($next_bin_rev);
$next = unpack("N", pack("B32", substr("0" x 32 . $next_bin, -32))); # decimal string to binary string


This works (tested with values of x up to 4 this time ;o) when start number is valid (has x "1"s in its string binary expression) and <> 0.
If start number equals 0 then next number in binary string expression is a string of x "1"s preceded by "0" as needed.

In essence, you replace part of the reversed binary string using the regular expression s/([0]*)([1])([1]*)([0])/\3\1\4\2/
(that's where Perl comes in handy even if this snipet is limited to 32 bits by pack/unpack functions).

Scales perfectly

 

[ledow]

Holy cow. You pose a simple boolean operator / binary string problem and some git manages to use a Perl regexp to get it done. That's like making people read Chaucer back to front before they learn their ABC's... I know I said *any* language but... :lol:

Anyway, thanks for the suggestions all - I'm doing some testing now on the various implementations and I'll get back to everyone once I find out what works well and what doesn't.

 

[ledow]

Here's another solution - cycle combinations of n bits

Pros: Less values to check
Cons: recursive function calls

I think we can safely say that this is the current leader. I couldn't get Gueben's to work properly - I just get junk out and it gets into infinite loops and all sorts. It's probably fixable, however. I didn't try the pre-computed tables ones because I would probably have to use Parkydr's algorithm to pre-compute them anyway!

On a 2GHz dual-core, my algorithm takes a big hit around the 300-340th iteration (i.e. the 340th number with 2 bits in its binary representation). It takes 18s of CPU time to get to 400. Parkydr's does it in 0.012s.

Whacking it up to the largest thing that a "long long" can handle (the 1953'th iteration), my algorithm probably wouldn't finish this side of Christmas... 2020. Parkydr's exhausts that within 0.09s. Making it do tons of different ones with different numbers of bits, I couldn't make it hit a second of computation time.

Those numbers are with unoptimised code, with the same number of printf's (which probably slow Parkydrs down a lot in comparison because it can barely write to the screen fast enough, while mine you can see the individual lines pop up on the screen one at a time after the 250th iteration).

The numbers scale in similar ways for other numbers of bits, so I think it's safe to say that Parkydr is currently out in front with his amazing recursive algorithm (I will have to check stack usage of such a thing, though, but to be honest, if I have to make a "fake stack" in RAM, it's worth it) which is orders of magnitude better than the naive example.

It's not that I don't trust you, Parkydr, but I have also double-checked the figures against my naive example to make sure that they are in fact correct and they appear to be.

Any other contenders or shall we all just beat Parkydr up?

 

[Geuben]

I'm a little annoyed mine didn't work, I'm tempted to try and get it working 2moro but I have other coding to do thats important!...I wonder why it didn't work, intrigued to know whether its just the implementation or if the maths I used to work it out is wrong.

 

[gbouilland]

Any chance you try the regexp idea even in C ?

There's no difference in execution time (< 1s) even with 6 bits and 10000 cycles...

If you prefer, I can send you a shell version :rolleyes:

 

[ledow]

If anybody's curious why I would need this, I'm currently writing a "puzzle solver" for the Mosco puzzle in STPPC2x, in the hopes of including it in the official distribution of these puzzles. Mr Tatham is quite finicky about stuff that gets into his codebase, and all I really need now is a real solver that can actually look at a Mosco puzzle and definitively decide whether it's solveable and/or how difficult it is for someone to solve (e.g. recursion depth, whether "guessing" is necessary etc.). A good solver is also crucial to form the basis of a good puzzle generator. This would allow us to do all sorts of things like add hints into the grid itself by partially filling it (and so make larger Mosco puzzles easier to solve for mere humans), omit clues that can be deduced logically (and so make smaller Mosco puzzles harder to solve), etc.

The way I have things working at the moment, this particular solver needs to build a tree of possibilities from a given position. I quickly realised that the easiest, cheapest (in terms of CPU/RAM) and quickest way to iterate over game possibilities is by doing it over certain "clues" that are given to the user around the edge of the puzzle.

These clues indicate how many "arrows" in the puzzle are pointing at that clue. That can be simplified, with the help of an array of all the squares that could be pointing at that clue, into a binary string of maximum length W + H - 1, where W and H are puzzle width and height (e.g. 7 on a standard 4x4). So a "4" clue can be represented as an ordered list of at most 7 puzzle squares (a 7-bit binary number) with 4 bits set in it. A set bit means that the arrow in that square IS pointing at that clue. A unset bit means it points elsewhere (it doesn't matter where, that's the beauty of this method).

By having a binary string like this for every clue (of which there are exactly 2W + 2H + 4 for any given puzzle), and a way to quickly generate every possible X-bits-set binary string of a given length, we can use boolean operators and very, very quickly build a tree of possibilities that show not only **a** solution (and thus that the puzzle is solveable), but every solution. It's also able to start with a half-filled random grid and see if it can be made into a solveable puzzle, etc. The beauty also is that the entire game possibilities tree does not need to reside in RAM at all but each part can actually be built dynamically when required (if this "next_binary_string_with_x_bits" function can be made fast enough which I think Parkydr's just done for me!).

So a 64x64 puzzle which will have 4096 squares, 260 clues, each affecting up to 127 squares can be analysed to give every single possible answer using no more than a few hundred KB of RAM and (hopefully) a few seconds of computation time on even the slowest machine. When you do things in a naive fashion, everything tends to be factorial-based, so the possibilities and memory requirements blow up far too quickly to do any sort of reasonable analysis of the game (hence the crappy generator/"solver" in Mosco at the moment).

Humans can probably only be bothered to do an 8x8 Mosco puzzle, but theoretically they can be of almost any size, so the solver needs to cope with even larger numbers. And because of the way these solvers tend to work to produce a solveable puzzle (splat some reasonable but random data into a grid and try, try, try until you find something that works), it should be possible to generate 64x64 and even larger grids on the fly with guaranteed solveability by deduction alone, getting every possible finishing layout, being able to analyse a half-full grid and provide the user with a "next logical step" hint, or point out logical errors, provide grids which would normally be way beyond human range but because of a clever generator it can insert certain hints that simplify any size puzzle to any level of difficulty required, and do so without filling RAM, hogging the CPU and allowing dozens of these calculations/solve-trees to be built every time the player moves.

My ultimate aim is to have a solver in Mosco that generates any size puzzle, makes it human-solveable, and at any time the user can press "hint" and get a real, useful hint about what they've done wrong or what they should look at next - even to the point that they can press hint every move and end up with a perfect solution.

To do that, I need a game tree. Storing every possibility in a normal tree structure to analyse things is stupid for anything past 8x8 and quickly blows up out of range of any memory you care to throw at it (taking the naive example - each square has 8 possibilities for the arrows it can contain, which generates 8x8x8 game possibilites, only about 5 or 6 of which are actually valid (there is more to take account of than just the clues, which adds greatly to the time taken for each possibility if you don't have nice binary data structures that you can just AND together to spot conflicts) out of 512 possibilities... larger games blow up even quicker. Now try and build this tree several dozen times for various attempts at creating a puzzle.

Thus, a game-tree in which any state can be generated by referring to an index number (e.g. the 1st possibility for clue 1, the 8th for clue 2, the 14th for clue 3, etc.) and then dynamically creating the real representation of that state when needed quickly is a great help. And with Parkydr's code, I'm able to do that - I just ask for the eighth string with 2 bits set or whatever (or, actually, I just recurse and call "next_binary_string_with_x_bits" instead, which gets me to the next step each time). Thus a game tree quickly becomes nothing more than W + H - 1 integers and all the complicated branching, sorting, pathfinding, etc. can be done extremely easily with little memory usage.

Things start becoming O(N) (equivalent to adding two N-digit numbers) instead of O(N^2) (equivalent to multiplying two matrices) or even (in some cases that I've run across) O(N!) which is a Big-O notation that no programmer wants to witness (solving the Travelling Salesman problem via brute force).

The only limiting factor I have so far is generating these bit-strings quickly enough to be useful on the GP2X. Now that problem appears solved, I can focus on the solver without having to memory-manage a dozen game-trees.

 

[ledow]

I'm a little annoyed mine didn't work, I'm tempted to try and get it working 2moro but I have other coding to do thats important!...I wonder why it didn't work, intrigued to know whether its just the implementation or if the maths I used to work it out is wrong.

It seemed to struggle with the loop:

while(((start >> 1) % 2) == 0)

which ends up hanging in an infinite loop with start=0. I was wondering if there was supposed to be a >>= instead and tried several combinations but everything I tried didn't work or just looked completely wrong. If I did get answers, they were immediately nonsense. I know the basic idea works, because I was toying with it myself before, but there's probably a tiny logical error in that code somewhere that blows things up.

Bear in mind that I invested all of about 10 minutes each to look at these bits of code and intend to review them all at a better time but for tonight, Parkydr's compiled first time, works more than fast enough for my testing and is written in C (which is where the final implementation will end up... his had a bit of C++ but it wasn't anything that couldn't be stripped out with no ill effects) and is good enough for me to carry on getting the other code that depends on that functionality finished.

This is one reason why I put in a nice function declaration - anyone is welcome to provide a function that does the job and I'll fight them out against each other should any sort of bottleneck in that function pop up (and might well do it just for fun anyway, because I couldn't find a function like this anywhere else on the net). The final function that goes into my code will be whatever one performs consistently fast over a wide range of input without needing special setup, crashing my machine or hogging RAM. My being able to actually understand what the internals of the function do is completely optional.

 

[TrevorBradley]

Oooh, math puzzle.. I wish I'd seen this earlier today.

Lemme go grab a piece of paper, my number theory text book and flip through it a bit. It would seem to me there should be a simpler mathematical rather than algorithmic solution....

Is there an upper limit to the number of 1 you're searching for? That seems to me to be the big choke point of any solution...

EDIT: Well, I can get you the sequence at least...

In pseudocode:

Given an existing number A in binary with N 1's...

1) Scan right to left, count the number of 1's (=n), searching for "01".
2) Invert "01" to "10".
3) Zero out previous portion of number right of this position, replace with ((2^n)-1)

If the number is all 1's, assume you can write it as 01111....111 -> 10111...111)

So basically...

1010010100101010101 ->
1010010100101010110 (no ones)

111101000000100000 ->
111101000001000000 -> (no ones)

100110 ->
101001 (one one)

110001111111110000 ->
110010000011111111 (eight ones)

I know C has some fancy byte shifting code, dunno if that's going to help here.

O(log2 A).. dunno if that's good enough for you.

 

[paeryn]

Trevor, I had the same idea and by the time I'd written it you'd mentioned it!

It assumes that start already has x bits set (you said it does, but your examples have start=0).
So it actually returns the next highest number with the same amount of bits as start.

CODE

int next_binary_string(unsigned int start)
{
unsigned int temp, skip, bit, result;

temp = start;
// Search for lowest bit set
bit = 1;
while (bit && !(temp & 1)) {
bit <<= 1;
temp >>= 1;
}
// Count consecetive bits set
// temp >>= 1; // replaced by bit-testing with &2
skip = 1;
while (temp & 2) {
skip <<= 1;
temp >>= 1;
}

result = ((start + bit) & ~(bit-1)) + skip - 1;

return result;
}

 

[TrevorBradley]

Trevor, I had the same idea and by the time I'd written it you'd mentioned it!

It assumes that start already has x bits set (you said it does, but your examples have start=0).
So it actually returns the next highest number with the same amount of bits as start.

GMTA. (I just can't bit shift numbers in C, it's been too long since I've coded in C)

From the original problem, it looks as if we're starting with a previous solution. And if not, if you scan through the number and find m 1's instead of n (m<n), scan through the number again right to left and convert all 0's into 1s until you reach the desired number of 1's. It's still O(log2 A).

I'd still love to find a mathematical rather than an algorithmic solution. I'm pretty sure I could do it if the number of 1's was fixed at 2 or 3. Let me sleep on it.

 

[paeryn]

I forgot to add, if the function returns a value that is less than start then the next bit-pattern requires a larger datatype.

Ledow: At the end of your original post you mention about working on 127-bit strings. That would need re-writing as long long is the biggest datatype and that's only 64bit.

 

[ledow]

Paeryn: Yes, the examples start at 0 but the code to handle this is trivially added into any of the above functions because it can be special-cased and save a lot of computation. So I don't mind functions that work or don't work with zero - basically:

if(start == 0)
return(2^x - 1)

However, the strict definition of the function required is that start will always have that number of bits set because it tends to make things a lot easier (and if I really need to, I could wrap calls to the functions and handle special-cases like this myself). Whether a particular implementation handles zero or not doesn't matter, but I wouldn't start off with just any other arbitrary "invalid" number (e.g. start = 255, x=1).

I'm just glad people are having so much fun with this...

Trevor: The number of bits set tends to be anything but has a "bulge" of popular numbers at just over half of the total string size in most cases - In fact, it's pretty much a perfect bell curve. So, if your routines work on 8-bit strings, expect about 4 of them to be set in the typical case. If your routines work on 256-bit strings, expect approximately 127 of them to be set in the typical case.

It's the way that the game works, in this case, but this thread is also likely to pop up on Google for anyone who needs something similar because I couldn't find anything like it.

You can see this if you run the Mosco game in STPPC2x (or, indeed, look at most "Magic Arrow Tile Puzzles" which is what they are based on). The clues tend to be about half the number of squares that they can be pointed at by.

CODE
X X X X X X
X . . . . X
X . . . . X
X . . . . X
X . . . . X
X X X X X X



Each of the X's can be pointed at by at most W+H-1 of the dotted squares (we'll ignore the "corner case", literally) and that's what we are trying to iterate in this particular exercise. We are generating binary strings of the .'s that could point at a particular X if they have an arrow (UL, U, UR, L, R, DL, D, DR) in them - a 1 means that a particular square points at that particular X. So in this 4x4 example, we are generating 7-bit strings where approximately half the bits are on , but it's possible for anything from 0 to 7 of them can be on.

Paeryn: About bit-sizes: Yes, but if I can find a generic, fast, algorithm, then the actual handling of larger strings will be a cinch.

If it means I have to use an arbitrary precision integer library or have to chop strings up into byte-sized chunks and write my own mul, pow, sum etc. functions, that's fine by me. But before I start doing that and hitting such problems, it's best to ensure that the algorithm I'm using is as fast as it can be reasonably made. If it's slow on a 4x4 (7-bits), then trying to scale is just stupid. But if something is super-fast on even 32x32 (63-bits), then if you have to take a performance hit on higher scales by introducing arbitrary precision, you're doing the best you can anyway.

I'm actually converting any code I test to "unsigned long long" (64bits) straight away, using a 0 return value as a special case to indicate that the algorithm failed to find a higher number (e.g. hit overflow, etc.). This gives me enough room to get more-than-decent-sized puzzles up and running and I can convert them to use larger ones if and when I need it. But first, if something doesn't scale to at least 8x8 (15-bit) or 16x16 (31-bit), it's pointless to consider it at the moment.

 

[TrevorBradley]

I forgot to add, if the function returns a value that is less than start then the next bit-pattern requires a larger datatype.

Ledow: At the end of your original post you mention about working on 127-bit strings. That would need re-writing as long long is the biggest datatype and that's only 64bit.

If we're doing bitwise math that only involves scanning the numbers, extending it to 127 bits shouldn't be a massive issue. Just store it as two long-longs, and be a bit careful around the boundary... And it's probably best to calculate and *store* everything as a bitwise numbers.. convert only to base 10 when absolutely necessary (if ever).

I actually had to do String based arithmetic for my game Factor. Fenix only has ints and floats, no longs or doubles, so doing arithmetic on 20-30 digit numbers got to be an issue... I had to write my own library for String based arbitrary precision multiplication. GP2X/Fenix handled it nicely, but I was only doing tens of calculations per second.

I'm looking forward to more math based games on the GP2X, I'm going to have to try this out...