Previous Page | Next Page
- by hcs at 4:23 AM EST on December 30, 2011
- I spent much of this week accomplishing one of my lifelong dreams, Mystify for NES.
Well, at least I've been dreaming of it since August or so, when I started writing it. Source.
- by nothingtosay at 9:19 AM EST on December 30, 2011
- I'll just say it. Best NES game ever?
- by hcs at 7:36 PM EST on January 3, 2012
- I have continued to work on this at every spare moment. It is faster now.
edited 7:38 PM EST January 3, 2012
- by Knurek at 2:07 AM EST on January 4, 2012
- Does anyone here has a cracked version of Pasofami emulator available here?
I'm asking since this emulator has a special tool which creates a working NSF file from a loaded rom and supports just about every Japanese Famicom/FDS game - would be really nice to have it to patch some holes in my NSF collection. :)
The version available for download is crippleware though - doesn't allow for any saving. :(
edited 2:07 AM EST January 4, 2012
- by hcs at 3:25 PM EST on January 13, 2012
- Went to an organ recital by Paul Jacobs last night at UCLA. One of the most striking pieces he played was La Présence multipliée from Messiaen's Livre du Saint Sacrement (played here by Olivier Latry).
edited 3:26 PM EST January 13, 2012
- by hcs at 6:41 PM EST on January 16, 2012
- Blip Festival Australia!
Not that I will be going (haven't been to any chiptune shows since blipfest 2008 and nowhere nearby), but I know we have a few Australians here and wanted to mention it for any who might consider it.
- by Josh W at 3:44 AM EST on January 17, 2012
- cool, that's like 5 miles from my apartment =D
- by hcs at 4:10 AM EST on January 17, 2012
- Do it! Looks like a good lineup, among the names I recognize, Trash80, Hally, Nullsleep all put on great shows. Bit Shifter was a little disappointing last I saw him at a Pulsewave, at Blip Festival he was quite good. And part of the fun is finding out what all these people you'd never heard of are up to.
edited 4:16 AM EST January 17, 2012
Some stuff from '08
edited 4:18 AM EST January 17, 2012
edited 7:25 PM EST January 17, 2012
- by hcs at 4:43 PM EST on January 25, 2012
- Nestify v6
Also I see that we have had our first genuine spam attack! Oh happy day!
edited 4:43 PM EST January 25, 2012
- by hcs at 11:39 AM EST on February 8, 2012
- Nestify v7 has been out for a while.
Last night I was thinking about Cantor's diagonal argument in the finite realm. The following is probably either well known or wrong, but I found it amusing.
For b or fewer numbers of b bits, you can use the diagonal method directly: choose a different bit from each number and invert it to build another number. If you have fewer than b then you can choose any values for the remaining bits; if you're constructing with ORs you can just leave 'em 0.
I was then thinking about 2^b-1 unique b-bit numbers (and here I think I'm remembering a job interview question that I bombed). At first I thought about subtracting each from the sum of all 2^b possible, and the value remaining would be the missing one. It turns out that you can do this a bit more simply, by XORing all the others together.
This works because if there were 2^b unique values, each column (place value) would use 2^(b-1) 0s and 2^(b-1) 1s. If a column is missing a 1, it will thus have 2^(b-1)-1 1s, an odd count, so the resulting XOR will provide the missing 1. If it is missing a 0, there will be an even number of 1s so the result of the XOR will be the missing 0.
I tried to see how this would extend to 2^b-2 unique numbers, but things begin to get a little more complicated. If you XOR all the numbers together, a 1 would indicate that the two missing numbers have a mismatch in that place, but we can't construct the two numbers directly from that. We may be able to use that fact in another way, though.
First, we can guarantee that there will be at least one 1 in the resulting XOR. From the argument above (the full 2^b unique values has an even number of 1s in each column), the result of XORing all 2^b must be all 0. For 2^b-2, then, the missing two values XORed together must give the same result as the 2^b-2, so that when these are combined the result is 0. Because we are dealing with unique values, these two cannot be the same value, so their XOR must have at least one 1.
A 1 in a result column must mean that there are 2^(b-1)-1 0s and 2^(b-1)-1 1s in that column, as that is the only way there can be an odd number of 1s among 2^b-2 unique values (2^(b-1)-3 1s would need 2^(b-1)+1 0s in that column, but there can be at most 2^(b-1) unique patterns among the other b-1 bits). So of the missing two, one must have a 0 and the other has a 1. We can find each of these by doing a second pass in the style of our approach for 2^b-1 unique values above, while treating the values with a 0 or with a 1 in that column as separate groups:
0. m is a fixed mask to select a bit that was 1 in the overall XOR result, u are the 2^b-2 given unique values.
1. v0 := 0, v1 := 0, these will accumulate the missing value
2. For each u[i] (i from 0 to 2^b-3)
2a. if m AND u[i] == 0, v0 := v0 XOR u[i]
2b. if m AND u[i] != 0, v1 := v1 XOR u[i]
It should be clear that this works in the same manner as above for the 2^c-1 values (where c is b-1) in each group, for the c bits besides the bit indicated by m. v0 will have a 0 in that bit, since it will be constructed from XORing 0s. v1 will have a 1 in that bit, since it will be constructed from XORing an odd number of 1s.
If we want to avoid the second pass, we can keep b pairs of accumulators on hand for the b possible masks (0 or 1 in each position) during the first pass, and at the end of the pass the XOR of all the values will tell us which of these actually contains the result (any of the positions with a 1 in the grand total XOR):
0. m[i] is a mask with bit i set, u are the 2^b-2 given unique values
1. v0[0..b-1] := 0, v1[0..b-1] := 0, these will accumulate possibilities for the missing value
2. a := 0, this is the overall accumulator
2. For each u[i] (i from 0 to 2^b-3)
2a. a := a XOR u[i]
2b. For each m[j] (j from 0 to b-1)
2b0. if u[i] AND m[j] == 0, v0[j] := v0[j] XOR u[i]
2b1. if u[i] AND m[j] != 0, v1[j] := v1[j] XOR u[i]
3. v0[i] and v1[i] (for any i where a AND m[i] != 0) are the missing values
This is of course more work overall, but there may be cases when we can only do one pass.
From this I'm getting a whiff of an approach to do this in general for 2^b-n uniques, but I haven't finished it yet. I also haven't actually tested any of it...
Previous Page | Next Page
HCS Forum Index
Go to Page 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
Search this thread
Show all threads
Reply to this thread:
Halley's Comet Software
Generated in 0.0224s;