Puzzling counting algorithm

VIRAND · 2008-10-23 22:35

I have a need to not only count two different ways but keep the counters aligned,
and also to be able to change either counter and have the other one change with it.
(I'm not talking about the CNT registers).
Think along the lines of gray codes and large integers. If either the gray code or the binary
is modified, then all you need is a shift and a XOR and the registers are re-synchronized.
In that case, it obviously would be a waste of time to clear and count up both registers to the new
value because there is a two step quick method.

But here is the counting system of the two counters.
The decimal count is really an ordinary binary count.
1 000111
2 001011
3 001101
4 001110
5 010011
6 010101
7 010110
8 011001
9 011010
... ..............
20 111000

Actually the second counter may be two or more longs. If the count starts with two longs,
one long will start all zeroes and the other will start all ones. This counting requires using
only numbers with equal zeroes and ones. Here is a rule I noticed for counting this way,
not based on math but just the observation of the pattern. To increment the funny counter,
Step 1. Start at the right side.
Step 2. Move left until there is a 01, then change it to 10.
Step 3. Move all of the 1's that were passed as far right as they can go.

What I need to do is be able to change the count on either side and get a fast translation
on the other side. Hopefully a translation that takes a constant amount of time to do, as with gray code.
It would be OK to start counting at 0 instead of 1 if that is somehow more correct.
NOTE: I realize that the translation process needs to know how many bits it has in this case that
starts with the lowest binary number and ends with the highest, WHICH HAVE EQUAL 0's AND 1's.
I believe there is another method where the number of bits doesn't matter, but forget about that for now.

Ideally, about half the HUB RAM may be used to hold these two counters that must always be in sync
even when either is arbitrarily changed. I believe that these counts are called "rank" and "permutation",
the first rank is the lowest permutation. The rank of the highest permutation happens to be the same
as the two numbers in the middle of the row of Pascal's Triangle on the row who's number is the same
as the number of bits in the permutation counter. The highest perm has all the ones on the left side.

But, if an algorithm or two works fast for translating between any "rank" and any "8 longs permutation",
that's a good start.

Please, Does anyone have ideas? I stretch to reach the solution and feel it's fur but can't grab it.
It may enable one of the most interesting Propeller applications, "if it works", and I know it can work,
because I've touched it from several different angles. I'm just not very advanced in math.
There is one other problem that I've been struggling to figure out and almost there, and that's the FFT,
which is not relevant to this.

Summary of the question: Translating between "n" and the "nth binary number with equal 0s and 1s",
given the number of total bits, which is necessary IN THIS CASE.

Curious what this is for? I'll make demos with a fast algorithm. It's one of those strange things about
math, like why do you need factorials to calculate logs and trigs, like why does the FFT use bit reversal,
like why do the mandelbrot and julia sets look the way they do, etc.

I can probably let loose one demo that took a whole night to calculate, but I am holding it back because
it is a distraction (at least to me) from figuring out how to define functions to correspond members of the
sets (of counting numbers, and of the numbers with a given equal number of zeros and ones).

I'll just tell a short story now. Once upon a time there was a man who built a time machine in a car with a flux
capacitor. To finish, he needed a special clock that had three different colors for three different time zones.
He asked his friend at the clock factory and he said "Sure, it'll be done in a week. By the way, what's it for?".
And after a few minutes of talking, the clockmaker said,
"I'm sorry, I'm afraid I can't do it. I don't believe I can possibly help you build a Time Machine".

KeithE · 2008-10-23 22:59

Well this won't be much help but...

If you don't get an answer, then you could try browsing through the Knuth fascicles on Combinatorial Algorithms for inspiration. This seems familiar. Some computer chess guys are very clever about this kind of thing, so you could try on talkchess.com. (See chessprogramming.wikispaces.com/Bit-Twiddling for some mind boggling stuff.)

Here are some fascicle links, maybe I've missed a few:

0a - 7         Introduction to combinatorial search
0b - 7.1.1     Boolean Basics
0c - 7.1.2     Boolean Evaluation
1a - 7.1.3     Bitwise Tricks and Techniques
1b - 7.1.4     Binary Decision Diagrams
2a - 7.2.1.1   Generating All n-Tuples
2b - 7.2.1.2   Generating All Permutations
3a - 7.2.1.3   Generating All Combinations
3b - 7.2.1.4-5 Generating All Partitions
4a - 7.2.1.6   Generating All Trees
4b - 7.2.1.7   History of Combinatorial Generation

KeithE · 2008-10-24 04:29

OK, here's a shot at a translation from a binary counter, to the virand counter.

Oops - I missed a detail, this doesn't do what you want, it skips a lot of numbers...

Let's say that we want to have a counter with b 1-bits set all the time, and let's have the binary counter start from 0 for simplicity.

To turn a binary count of n, into a virand count n'

n' = 2^(n div b) * ((2^(b+1)-1) - 2^(b - n mod b))

Let's take the case b=4

The (2^(b+1) - 1) term is a constant, 15 or %1111

n div b is easy if b is a power of 2, just a right shift
n mod b is easy if b is a power of 2, just a bitwise and
Multiplying by 2^(n div b) is just a left shift

If I got that right, then I think that turning n' into n could be done by finding the least significant 1 bit (bits.stephan-brumme.com/lowestBitSet.html is one idea), shifting that down to bit 0, and then finding the least significant 0 bit. Finding the least significant 0, is the same as inverting and then finding the least significant 1 bit. Maybe the floating point code has some examples of this sort of thing. Isn't this done when normalizing? Or maybe there's an easier way...

I still think that Hacker's Delight might have something relevant, but I don't have a copy here. I think that hakmem 175 covers incrementing n'.

groups.google.com/group/programming-puzzles/browse_thread/thread/1a418e74f31527b1

C code based on 2-1 of Hacker's Delight.

www.hackersdelight.org/HDcode/snoob.c

Unfortunately page 14 is not in the google books preview:

books.google.com/books?id=iBNKMspIlqEC&printsec=frontcover&dq=hacker%27s+delight#PPA13,M1

They discuss that this could be used to iterate through subsets of a given size. Maybe searching with this will turn up other information - Knuth might cover it. Or you could offer it as a suggestion, and get a check

Post Edited (KeithE) : 10/24/2008 4:44:28 PM GMT

evanh · 2008-10-24 11:26

Is the "counter" label actually relevant? Are we talking about exclusively handling in(de)crements of one or is this meant to handle any change in value from either side? For that matter is a change in value relevant at all?

hippy · 2008-10-24 13:19

I'm not sure I actually understand what you want but if you want fastest translation from a decimal count to a balanced-ones-and-zeroes value and vice-versa it seems two lookup tables would do the job; depends on what the maximum number of bits required is as to how practical that is to implement.

Populating the lookup tales is easy, particularly in PASM. Increment the balanced value, use TEST with WC to check if an odd number of bits, increment again until there isn't.

PRI PopulateLookupTables | d, b
  b := 0
  repeat d from 1 to 20
    repeat while OddBitCount( ++b ) 
    decimalToBalanced[noparse][[/noparse] d ] : = b
    balancedToDecimal[noparse][[/noparse] b ] : = d

That algorithm would work for converting each way but doesn't have a constant conversion time. Though one can delay so they all take as long as the worse case.

PRI GetBalancedFromDecimal( d ) : b
  repeat d  
    repeat while OddBitCount(++b)

PRI GetDecimalFromBalanced( bx ) : d | b
  b := 0
  d := 1
  repeat   
    repeat while OddBitCount(++b)
    if b == bx
      return d
    d++

VIRAND · 2008-10-24 20:29

KeithE, your math looked like what I wanted but it's too bad it skipped by apparently failing to do step 3, (not pressing together all the passed ones under the 01-->10 swap). BTW, Although I haven't tried it yet, the MEMHAK 175 algorithm looks very elegant compared to my 3-step algorithm for incrementing the V-counter. Thanks.

@hippy: The lookup table idea has come up elsewhere, but is probably only useful for the leaves of a recursive algorithm, because the desired numbers would, if stored (and there is compelling evidence that storage is unnecessary) could require one megabit per table entry!

evanh said...
Is the "counter" label actually relevant? Are we talking about exclusively handling in(de)crements of one or is this meant to handle any change in value from either side? For that matter is a change in value relevant at all?

Essential! This is part of a sound-learning algorithm which has a complete definition of all "sound" already, so it doesn't use any additional memory to store learned sounds. The labeling counter is used in the process of selecting a sound for recall. The V-counter only predicts ALL "perfect" 1-bit sounds that can be output serially through a Propeller sound pin.

It is interesting that this kind of algorithm is associated with Chess, as one of my friends who is fascinated by it, has hypothesized that it could, with a simple formula, "learn" to play "perfect" games of Chess AND/OR Checkers, and also that besides my own imagination, I would give credit to Alan Turing and David Champernowne for the basis concepts.
As a game AI, it would in constant time output a game board with a "best move" in response to an input board, without any logical analysis of those states, nor sense of progress in time; therefore it could play 6 billion games simultaneously and probably win almost all of them.

This is an early automated demo which was the first exploratory probe into this soundspace, and also happens to be my first significant STEREO intangible soundspace player output. See my HYDRA miscellaneous demos for some of the earliest examples of my intangible sound sources. (It's not like you could use my original TRS-80 code.)
ultravires.net/1stereo.mp3

I have also demonstrated the use of the Champernowne Constant in binary and decimal for this purpose, such that it can be used as the basis of calculating numbers like this: (Avoid opening in "Notepad", other editors ok.)
ultravires.net/POCKET.TXT
Which SOUNDS like this: (TURN UP THE VOLUME BEFORE LISTENING AND TURN IT DOWN AFTERWARDS)
ultravires.net/POCKET.WAV
My use of large binary and decimal integers for digital sound verifiably preceded the invention of MP3 (and maybe CD)!
(Although I assume the same is true of all those PDP system algorithms KeithE gave me links to.)

evanh · 2008-10-24 21:57

My question was a lot simpler than that. What sort of changes occur to each counter?

And you are hinting there is some sort of edge detection needed?

VIRAND · 2008-10-24 23:43

evanh said...
My question was a lot simpler than that. What sort of changes occur to each counter?

And you are hinting there is some sort of edge detection needed?

The ordinary counter has almost no constraints on it's changes. Consider it the integer-only accumulator of an arbitrary precision calculator.(*) Logical operations are also allowed.

The V-counter has only one restraint: It CANNOT (at present) have an unequal amount of 0's and 1's. You may make the assumption that it is capable of being used as a sound recording buffer in spite of that limitation. In that case, the ordinary counter would know right away which predefined and predictable sound was "recorded".

I cannot think of a current relevance of edge detection here.

(*)The POCKET files are seriously and literally self-explanatory. Both contain the same number. The Sound file allows that number to literally speak for itself, as to why it exists, and what I am doing. Except that now I'm only using binary, not decimal.

KeithE · 2008-10-25 18:49

Here's some additional snoob (same number of one bits) discussion, and reverse snoob:

http://forums.parallaxinc.com/chessprogramming.wikispaces.com/Traversing+Subsets+of+a+Set

Puzzling counting algorithm

Comments