Negative Base | Hacker News Reader

Negative Base

en.wikipedia.org

177 pointsint_10h69 comments

When I was part of an organization in college, part of the onboarding process was that each applicant had to have a conversation and (possibly) do a "quest" for each member. My standing quest was that I would write the first 12 or so numbers in negabinary on my whiteboard, and have them determine the next few numbers and explain what they meant. I had people sitting outside my room for hours trying to figure it out. A few did do it, and normally had some expletives for me afterward.

I bet they were frustrated. I was thinking of the various puzzles online trying to understand a sequence of numbers when I read about this, and realizing there's no way I'd ever have come up with the answer on my own.

Looking at the table is bad enough, but I imagine most people looking would think "Aaah binary" and convert to decimal: 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28... That's cruel :)

I probably got a little too much sadistic pleasure out of it, yes...

However, I was always willing to answer nontrivial questions, and even convert numbers to/from negabinary to help them. (The program used the Schroeppel2 implementation, to prevent them from getting too much of a clue if they somehow managed to find its source code)

Looking at the sequence of negabinary representations, I could imagine (with the benefit of hindsight) that it wouldn't be too hard to guess the next numbers in the sequence. You'd just need to make a few observations: the rightmost digit always flips from 1 to 0. The second digit from the right reads one twice, then zero twice, etc. When you increase the length of the sequence, add two leading ones.

I'm not sure those would be enough, but just inspecting the digit-wise patterns would get you pretty far. Correctly interpreting the sequence is far harder!

Yup, the actual challenge was to interpret the sequence, not just produce the next number. I recall a few people starting on that track though.

It seems to me like the n-th number repeats 2^n times, with 1 being in the middle of each sequence. From this, you could get the 13th number quite easily. Interpreting it would be a lot more difficult though.

Interestingly, normal binary has the same pattern, but with different offsets for the start of the sequence.

Reading those as normal binary, apparently there's significant overlap between the negabinary sequence and the sequence of n XOR 10:

https://oeis.org/search?q=1%2C+6%2C+7%2C+4%2C+5%2C+26%2C+27&...

I remember when negative zero was labelled a hoax. (-:

* https://en.wikipedia.org/w/index.php?title=-0&diff=25603603&...

* https://en.wikipedia.org/wiki/Wikipedia:Articles_for_deletio...

Best way to represent nil, in my opinion ;)

Although it smells like a design flaw (which negabinary conveniently doesn't have)

Are there common languages where -0 != +0? Or are you implying that this would be a good decision when creating a new language?

basically every language with IEEE-754[1] compliance..!

[1] - https://en.m.wikipedia.org/wiki/IEEE_754

But only when imposing a total ordering.

that’s not the case, in IEE754 floating point, zero is signed - i.e negative and positive zero are distinct values

But the standard comparison operators don’t distinguish them.

I'd think that in all those languages, -0 == +0 tests true, though. In JavaScript even -0 === +0 tests true.

The only way to tell them apart in general is to divide by them. In some languages you might be able to type-pun and examine the bit pattern, or do things like Object.is() or whatnot.

javascript:

    > 1/(-0)
    -Infinity
    > 1/0
    Infinity
    > Object.is(0, -0)
    false

Of course = doesn't actually test equality in javascript. == reports -0 as being equal to +0, but Object.is reports them as different.

See now, I contest this particular defense because it groups together 'javascript' and 'good decision'.

I think that's the first time I've ever seen someone use INTERCAL code to try and explain a concept.

For those wondering, please do read the Wiki article[1]. It's amazing.

[1] https://en.wikipedia.org/wiki/INTERCAL

See also balanced ternary [1].

[1] https://en.wikipedia.org/wiki/Balanced_ternary

Which you can use to solve the puzzle:

"You have 12 coins that all look exactly the same. One is counterfeit and is either heavier or lighter than the other 11. With a balance beam scale, isolate the counterfeit coin in three moves."

Any uses for Negative-base systems?

Hoo, that's one of my favorite puzzles - there was a version of it on Brooklyn Nine-Nine with no solution given, which ruined my sleep that night. I have a theory that it's actually a little harder for programmers than for other technically inclined people because the instinct to treat it as a kind of binary search problem is really hard to shake.

Is it not a binary search problem?

I don't want to give too much away but consider that if you start by weighing 6 coins against the other 6, you already know what's going to happen.

Wrong. You don't know which side will be heavier

No, it is a ternary search problem.

EDIT: According to

> https://en.wikipedia.org/w/index.php?title=Balance_puzzle&ol...

if you know that one coin is different from the others, with 3 weighings, you can even detect it among 13 coins (not just 12).

Nope. It's ternary in nature. The subproblem of "You have 3 coins, one of which is lighter than the others. On a balanced scale, figure out which one is lighter in one weighing." is a good place to start. Just enumerate all 3 possible weighings and you should be able to see the correct approach.

How do you solve this?

ABC, one of them is different weight than the other two (either more or less)

Possible ways to weigh them:

  A v B
  A not enough information
  E C is odd one out
  B not enough information

  A v C
  A not enough information
  E B is odd one out
  C not enough information

  B v C
  B not enough information
  E A is odd one out
  C not enough information

  AB v C
  AB not enough information
  E C is odd one out
  C C is odd one out

  AC v B
  AC not enough information
  E B is odd one out
  B B is odd one out

  BC v A
  BC not enough information
  E A is odd one out
  A A is odd one out

In all possible ways to weight 3 coins, all have uncertainty which means you cannot deduce which is the odd one out.

Your OP stated one is lighter, not one is different.

It's easier than the 12-coin one different puzzle, but introduces the ternary concept well enough to get you started on the harder problem (there are some other complications to it as well).

Weigh 2 coins. If the scales move you've found the lighter coin. If the scales balance, it's the third coin you didn't weigh.

Ah I got the original (12 coins, one is lighter or heavier) mixed up with 3 coins (one is lighter).

Label each coin, divide in three stacks each time, and shuffle meaningfully each time the subsets, to remove uncertainty.

Not really - you can reduce it to one but you don't quite have enough information.

So I think it goes like this:

- you have 12 coins, and each one has an equal chance of being heavier or lighter than the others - so that's 24 possiblities

- you have 3 moves, and the result of each move could be one side of the beam goes down, one side goes up, or it balances. That means you can create a system that identifies 3^3 = 27 outcomes. So far so good.

- you need each of your outcomes to provide real information. if it was a binary problem that means you're not really getting any information if the beam balances

(bit sketchy on that last point, maybe someone can help with that)

Yeah, the reason I suspect it tends to thwart programmers (if I recall correctly) is that there's a solution that looks a lot like binary search that _almost_ works, but the actual solution looks very different from it at every step. So the programmer will start with the one that looks like binary search, realize that it provides almost enough information, and try to squeeze a little more out of it by modifying it in little ways, when they sort of need to go back to the drawing board instead.

"that means you're not really getting any information if the beam balances"

Wrong. If it was true, that would imply that the probability of it balancing is 1, since the information you get is -log2(probability). Obviously the probability of it balancing is lower than 1, so you do get information.

You don't get any information if the probability of the beam balancing is either 1 or 0. If you put everyone on the scale, the probability that it will be balanced is 0 - you don't learn anything. So the trick is to exclude some of the sample group in every measurement. You can use a binary search strategy where you divide the coins into "on the scale" and "not on the scale" groups, until you have a set of two that definitely contains the one you're searching for (and then one more measurement will tell you which one of those two it is) - but that strategy requires too many measurements, so you need to use more information at each stage, and you can't throw out coins you've determined to be non-counterfeit.

Traditionally binary search involves recursively dividing the options into two roughly equal sized groups and then using a measurement to rule out every member of one of the groups (and thus half of the search space) with every step. The solution to this problem differs from that approach in certain key ways.

It is a kind of search problem, but the steps aren't recursive and you have to use several tricks to maximize the information you get out of each measurement.

Pretend you only had 3 coins. The idea is -- when you use the scale to measure 2 coins against each other -- you actually gain "information" about all three coins.

This is because there are 3 possible scenarios:

1. the biased coin is on the right side of the scale,

2. the biased coin is on the left side of the scale,

3. or the biased coin is the coin not measured (since the scale is balanced).

In essence, even though this scale only has 2 sides, you gain information proportional to having 3 sides.

Hence if we were to extend this to a scenario where you had n coins, of which one was biased and others fair, you would only need log_3 n measurements total to find the biased coin.

This idea has pretty neat applications. For example, if you wanted to prove that merge sort has a O(n log n) computational complexity, you can use this scale idea.

I'm going to have to take this riddle bait. My solution:

Move 1: weigh 6 coins vs 6 coins. Isolate the heavier set for the next move. Move 2: weigh 3 coins vs 3 coins. Isolate the heavier set for the next move. Move 3: weigh any two of the 3 remaining coins. If one is heavier, that is the counterfeit. Otherwise (if coins are equal in weight) the remaining coin is counterfeit.

You failed because:

> One is counterfeit and is either heavier or lighter

It turned out the counterfeit was lighter and you discarded it after the first weighing.

Ahhhh... hmm. I thought it seemed too easy.

Here are multiple solutions to the problem explained pretty clearly: http://mathforum.org/library/drmath/view/55618.html

This was a fun one to work out on paper though.

Can anyone provide some examples of practical applications of this?

I can’t imagine there ever would be.

Well, the number of digits tell you the sign of the number, right? It could save a sign bit

I think the ideal wikipedia page for this kind of thing has a 'Properties' section from which to start thinking about this

The bit saved for the sign is lost because you need more bits to represent a number.

True, and it seems you actually need exactly one extra bit for all positive numbers

I don't think anyone ever imagined a use for imaginary numbers either, but those turned out to be quite useful for reducing dimensionality. Towards the bottom of the article it states that Donald Knuth proposed imaginary base numerical systems.

So this may eventually find a use, likely with higher-dimensional math.

It will be really funny if there is some bit of new, undiscovered physics, that went undiscovered for so long just because it's best described using some esoteric maths like complex base numbers.

Highly unlikely, but fun to think about.

Are there any examples where the representation of a number matters in physics?

I recall some effort in moving from imperial measurement to metric. Reality itself does not care, but the math sure gets easier if you carefully select units.

Actually, another neat example is analog vs digital computation. your models can get very different answers. I recall some Mandelbrot guy talking about that.

See Gaussian (cgs) units for an example, compare Coulomb's law in cgs and SI: https://en.wikipedia.org/wiki/Gaussian_units#Unit_of_charge

Imaginary numbers were useful as soon as they were invented. They are algebraically closed, unlike the real numbers, and are required for the fundamental theorem of algebra.

https://en.m.wikipedia.org/wiki/Fundamental_theorem_of_algeb...

The first use of negative roots was to find the (real) roots of certain polynomials. They were considered a mathemathical hack: useful, but specious on their own. And then it turned out that if you take them on their own terms, they're fantastically useful.

In addition to the other points, imaginary numbers immediately added to the representation of things we could represent. Simply rewriting existing numbers in other ways isn't all that interesting; it doesn't add anything. We already knew there's an infinite number of ways to serialize numbers to symbols. Negative base numbers don't behave differently than positive base numbers, because "negative base numbers" and "positive base numbers" are artifacts of English and don't actually exist mathematically. There are numbers, which are written in different representations, but are not actually different entities.

So there's no possible way this could be useful for "higher dimensional math" or anything, because there's no entity being added here. Higher dimensional math already uses numbers. At most there might be one or two concepts that might in some manner if you squint hard enough could be better represented by negative base numbers, but even then the positive base representation would probably still be how people actually understood it.

> At most there might be one or two concepts that might in some manner if you squint hard enough could be better represented by negative base numbers,

That's what I was thinking.

So in your mind people are just coming up with these things for no reason, is that it?

It’s fun and interesting to figure out. There are lots of ways to represent numbers but they don’t change the thing they represent.

> There are lots of ways to represent numbers but they don’t change the thing they represent.

Different representations of the same thing are not useless; one might make an argument (which I can only back up off the top of my head with mathematical examples, but I suspect that there are also many in the physical sciences) that they are at the root of much progress. The canonical example is to try to do positive-integer arithmetic with Arabic versus Roman numerals; they represent exactly the same thing, but I'll bet you can compute 16 ⨉ 17, but not XVI ⨉ XXIII (without converting), in your head.

    XVI ⨉ XXIII
  = XVI ⨉ (XVI + I)
  = (XVI ⨉ XVI) + XVI
  = CCLVI + XVI
  = CCLXXII

I didn't say that it wasn't computeable, only that I bet you couldn't do it in your head.

Note that your calculation for some reason (EDIT: ah, maybe because my Arabic-numeral problem has 16 ⨉ 17?) replaces XXIII = 23 by XVII = 17, and then black-boxes the calculation XVI ⨉ XVI = CCLVI (which I at least wouldn't know without converting).

I agree. You can use the same algorithm for computing both. But Arabic has better constants. Because it's a discrete convolution instead of grouping and aggregating.

      1 6
    1 1 6
    7 7 42
    1, 6+7, 42 = 100 + 130 + 42 = 272

Same process in Roman

      X V I
    X C L X
    X C L X
    I X V I
    I X V I
    I X V I
    CC LL(=C) XXXXX(=L) VVV(=XV) III = CCCLXVIII = 16*23=368

This supports the arguments that Arabic numbers really are better suited for things like multiplying. They don't have the property that multiplication is convolution, so you can't even do things like truncate your computation to get an approximation.

There's probably a way to formalize this with an entropy argument: that roman numerals are inefficient encoding. Because given some n-length string of numerals, firstly many are invalid encodings, and secondly among the valid numerals there isn't a uniform distribution from strings to integers. Something like that.

> I agree. You can use the same algorithm for computing both.

Although it's in some sense the same algorithm, the Roman-numeral version requires far more memorisation. For example, once I know that 2 ⨉ 3 = 6, I know without further memorisation (or, rather, with only a meta-memorisation that generalises readily to other contexts) that 20 ⨉ 30 = 600; but, even once I know that II ⨉ III = VI, I have to memorise separately that XX ⨉ XXX = DC.

> This supports the arguments that Arabic numbers really are better suited for things like multiplying. They don't have the property that multiplication is convolution

I think "They" here is "Roman numerals", not (as the structure seems to suggest) "Arabic numerals", right?

Science need not necessarily have any practical use. That’s why it is called Science. Science, the way I define it is: Study for the sake of it.

- Riddles.

- Obfuscation.

- Storing signed numbers in unsigned fields (nah, not really).

“An intellectual is a person who has discovered something more interesting than sex.”

― Aldous Huxley

Taken one step further, could you have irrational bases?

i^1 = i

i^2 = -1

i^3 = -i

i^4 = 1

https://en.wikipedia.org/wiki/Complex-base_system

thank you!

How do you divide by numbers other than -2?

Reply on news.ycombinator.com