Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Negative Base

en.wikipedia.org

Post reply on HN
Print view View original

61–70 of 74 posts

Re: Negative Base

#61

Post by grive »

emilfihlman wrote: post #55
phamilton wrote: post #30

Earlier quoted context omitted.

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 on…

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

Re: Negative Base

#62

Post by emilfihlman »

scrooched_moose wrote: post #59
emilfihlman wrote: post #55

Earlier quoted context omitted.

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 on…

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).

Re: Negative Base

#63

Post by xelxebar »

msoucy wrote: post #15

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.…

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&...

Re: Negative Base

#64

Post by saagarjha »

foxhill wrote: post #57
pphysch wrote: post #54

Earlier quoted context omitted.

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.

Re: Negative Base

#65

Post by foxhill »

saagarjha wrote: post #64
foxhill wrote: post #57

Earlier quoted context omitted.

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

Re: Negative Base

#66

Post by kybernetikos »

pphysch wrote: post #54
pmarreck wrote: post #41

Earlier quoted context omitted.

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?

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.

Re: Negative Base

#67

Post by saagarjha »

foxhill wrote: post #65
saagarjha wrote: post #64

Earlier quoted context omitted.

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.

Re: Negative Base

#68

Post by QML »

TrinaryWorksToo wrote: post #26
catpolice wrote: post #22

Earlier quoted context omitted.

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?

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.

Re: Negative Base

#69

Post by gkfasdfasdf »

philbarr wrote: post #18
Sharlin wrote: post #10

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?

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.

Re: Negative Base

#70

Post by bzbarsky »

foxhill wrote: post #57
pphysch wrote: post #54

Earlier quoted context omitted.

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

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.

Post reply on HN