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

51–60 of 74 posts

Re: Negative Base

#51

Post by JadeNB »

jjaredsimpson wrote: post #49
JadeNB wrote: post #37

Earlier quoted context omitted.

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

> 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?

Re: Negative Base

#52

Post by retzkek »

jfoutz wrote: post #46
throwaway37585 wrote: post #45

Earlier quoted context omitted.

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

Re: Negative Base

#53

Post by rocqua »

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

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.

Re: Negative Base

#54

Post by pphysch »

pmarreck wrote: post #41
JdeBP wrote: post #9

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?

Re: Negative Base

#55

Post by emilfihlman »

phamilton wrote: post #30
TrinaryWorksToo wrote: post #26

Earlier quoted context omitted.

Is it not a binary search problem?

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.

Re: Negative Base

#57

Post by foxhill »

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?

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

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

Re: Negative Base

#58

Post by msoucy »

soVeryTired wrote: post #39
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.…

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

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.

Re: Negative Base

#59

Post by scrooched_moose »

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…

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.

Re: Negative Base

#60

Post by [deleted] »

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…

[deleted]
Post reply on HN