4 ms·

Counting the Hard Way

80 points by fildon 3y ago

peter_d_sherman 3y ago
>"The Quarter-Imaginary numeral system was first proposed by Donald Knuth in 1960. The trick with this base is recognising that powers of 2i "rotate" through the Gaussian plane." Powers: -1: -(1/2)i, 0: 1, 1: 2i, 2: -4, 3: -8i, 4: 16, 5: 32i, 6: -64 etc. PDS: Now this is highly interesting to me! A system which collapses a 2D number system, that is, non-imaginary + imaginary numbers (AKA, the "Complex (2D) Plane") -- back into what is basically a number line -- or a single-dimensional linear system (choose whatever terminology or linguistics you prefer...) But the point is -- it reduces dimensionality from N to N-1 dimensions -- while still preserving imaginary numbers... To accomplish this weird trick, Knuth spaces out imaginary numbers (and negative numbers) at intervals of 4 -- basically you cycle through properties (positive real, positive imaginary, negative real, negative imaginary) with every cycle of 4. Could this be accomplished with other bases and other number systems having more than one dimension? Based on Knuth's example, it would seem to be very possible! I can only wonder what interesting mathematical properties future mathematicians might discover by using such structures... They might turn out to be useful for a lot of things! I'd be highly curious if there is any Mathematician who has applied such a structure to one or more specfic problems, and if it helped them solve a specific problem in an elegant or novel way... What would also be interesting would be a list of mathematical problems (like a wiki page) whose computation could be aided by using such a structure, and how specifically to perform calculations using the structure, etc., etc.
- colanderman 3y ago
  > Could this be accomplished with other bases and other number systems having more than one dimension? Yes, all sets ℤⁿ (n > 0) have cardinality ℵ₀ and therefore a bijection can be defined for any set ℤⁿ↔ℤ. The "computer science" way to think of this is, you can always e.g. interleave the bits of any number of integers, to encode them as a single unique integer. For two dimensions this is the Z-order curve [1]. [1] https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
  - peter_d_sherman 3y ago
    Never would have thought of the relationship between this and the Z-order curve -- but yes, upon consideration, I see the relationship! Brilliant!
- WastingMyTime89 3y ago
  Nothing surprising here. The cross products of countable set are countable and a bijection between N and NxN which you can then extend as been known for ages. The whole thing falls apart as soon as you use continuous set.
  - chr1 3y ago
    The cross product of continuum sets is also equivalent to a continuum, so it does not fall apart, it forms a space-filling curve on complex plane. See z-curve section of https://en.m.wikipedia.org/wiki/Quater-imaginary_base https://en.m.wikipedia.org/wiki/Quater-imaginary_base
    - WastingMyTime89 3y ago
      You learn something everyday. For whatever reason I was convinced there was no bijection between R and its cross-products which is extremely wrong.
  - rocqua 3y ago
    It is quite surprising to most people when they first learn that there are more real numbers than there are integers, but there are just as many pairs of integers as there are integers. In other words, infinity*infinity=infinity whilst 2^infinity>infinity The proofs are pretty easy, but that doesn't make the result less surprising to people who don't know it yet.
- shoo 3y ago
  Another example of this kind of thing is demonstrating that the set of rational numbers are countable. Each rational number has the form a / b for a pair of integers (a, b). This representation could be non-unique, e.g. 1/2 = -3/-6 are two different representations of the same rational number as fractions of integers. For this representation to be unique let's require the denominator b to be positive and a, b to have no common divisor. Let's consider (a, b) a point with integer coordinates on the lattice Z x Z, where Z is the set of integers (Z = { ..., -2, -1, 0, 1, 2, ... }). We can count each of these points if we begin by labeling the origin (0, 0) as "0" then (1, 0) as "1" then (0, 1) as "2",(-1, 0) as "3", etc. We can order these integer lattice points first by their increasing magnitude |a| + |b| from the origin and then by the angle they make relative to the origin and count them all one by one. Informally this shows that the set of rational numbers is not larger (in the sense of cardinality) as N_{>=0}, the set of non-negative integers. It's not smaller either as the set of non-negative integers N_{>=0} are a subset of rational numbers.
kybernetikos 3y ago
Factoradic is another interesting number system I've occasionally had reason to use. It's handy for counting permutations.
ithkuil 3y ago
Obligatory reference to Dimitri's Combo Class: https://youtu.be/GWA_NraxOUw https://youtu.be/GWA_NraxOUw https://youtu.be/hI-pwt7LyUw https://youtu.be/hI-pwt7LyUw https://youtu.be/MM0Sbfvf2Hw https://youtu.be/MM0Sbfvf2Hw
Out_of_Characte 3y ago
Stuff like this makes me feel like the base10 system might eventually get replaced by an even more usefull counting system.
- cassepipe 3y ago
  Does it not boil down to a tradeoff between the amount of symbols you are willing to learn and the space you want to use to write a number down ? Base 10 strikes me as good tradeoff
  - Qem 3y ago
    Also a tradeoff with the size of the arithmetic tables one has to learn by rote. It scales with n^2. 100 entries in base 10, and just 36 in base 6, for example.
  - avhon1 3y ago
    ...and also the number of integer factors of your base. 10 only has 1, 2, 5, and 10. Bases 8 and 6 have just as many. Bases 12 and 60 (used by the Sumerians and Babylonians) offer more convenient divisors.
- Spivak 3y ago
  Base 12! The operations humans do a lot divide by 2,3,4,12 can be done evenly. Your goal is to pack as many factors into your base as possible. They're called highly composite numbers and their big brother superior highly composite numbers. Base 10: 1,2,5,10 Base 12: 1,2,3,4,6,12 Base 60: 1,2,3,4,5,6,10,12,15,20,30,60 https://en.m.wikipedia.org/wiki/Superior_highly_composite_number https://en.m.wikipedia.org/wiki/Superior_highly_composite_nu...
  - Qem 3y ago
    Children starting school would not be amused needing to learn 144 entries arithmetic tables. Lots of people were scarred already, starting with a lot of resentment against math due to sheer boredom of rote learning 100 entries tables close when they are first presented to the subject.
taeric 3y ago
Knuth's volume that goes over different number systems was a ton of fun. Goes over some of the interesting ideas behind such things as two's compliment numbers, as well. That is, even within the same base, you can have different ways of doing things. "Balanced ternary" is the one that seems like it had the most potential outside of binary, in a computer. That ship has firmly sailed, at this point.
sdenton4 3y ago
I'm a big fan of the Fibonacci base: https://en.m.wikipedia.org/wiki/Fibonacci_coding https://en.m.wikipedia.org/wiki/Fibonacci_coding It has the nice property that it's a) binary, and b) each number contains a '11' substring at the end, but nowhere else. This makes it slightly less efficient than the usual base 2 binary, but handles variable length integers nicely; you always know where one number ends and the next begins, so you don't have to worry about overflow or specifying the length of a number.

80 points by fildon 3y ago

>"The Quarter-Imaginary numeral system was first proposed by Donald Knuth in 1960. The trick with this base is recognising that powers of 2i "rotate" through the Gaussian plane." Powers: -1: -(1/2)i, 0: 1, 1: 2i, 2: -4, 3: -8i, 4: 16, 5: 32i, 6: -64 etc. PDS: Now this is highly interesting to me! A system which collapses a 2D number system, that is, non-imaginary + imaginary numbers (AKA, the "Complex (2D) Plane") -- back into what is basically a number line -- or a single-dimensional linear system (choose whatever terminology or linguistics you prefer...) But the point is -- it reduces dimensionality from N to N-1 dimensions -- while still preserving imaginary numbers... To accomplish this weird trick, Knuth spaces out imaginary numbers (and negative numbers) at intervals of 4 -- basically you cycle through properties (positive real, positive imaginary, negative real, negative imaginary) with every cycle of 4. Could this be accomplished with other bases and other number systems having more than one dimension? Based on Knuth's example, it would seem to be very possible! I can only wonder what interesting mathematical properties future mathematicians might discover by using such structures... They might turn out to be useful for a lot of things! I'd be highly curious if there is any Mathematician who has applied such a structure to one or more specfic problems, and if it helped them solve a specific problem in an elegant or novel way... What would also be interesting would be a list of mathematical problems (like a wiki page) whose computation could be aided by using such a structure, and how specifically to perform calculations using the structure, etc., etc.

colanderman 3y ago
> Could this be accomplished with other bases and other number systems having more than one dimension? Yes, all sets ℤⁿ (n > 0) have cardinality ℵ₀ and therefore a bijection can be defined for any set ℤⁿ↔ℤ. The "computer science" way to think of this is, you can always e.g. interleave the bits of any number of integers, to encode them as a single unique integer. For two dimensions this is the Z-order curve [1]. [1] https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
- peter_d_sherman 3y ago
  Never would have thought of the relationship between this and the Z-order curve -- but yes, upon consideration, I see the relationship! Brilliant!
WastingMyTime89 3y ago
Nothing surprising here. The cross products of countable set are countable and a bijection between N and NxN which you can then extend as been known for ages. The whole thing falls apart as soon as you use continuous set.
- chr1 3y ago
  The cross product of continuum sets is also equivalent to a continuum, so it does not fall apart, it forms a space-filling curve on complex plane. See z-curve section of https://en.m.wikipedia.org/wiki/Quater-imaginary_base https://en.m.wikipedia.org/wiki/Quater-imaginary_base
  - WastingMyTime89 3y ago
    You learn something everyday. For whatever reason I was convinced there was no bijection between R and its cross-products which is extremely wrong.
- rocqua 3y ago
  It is quite surprising to most people when they first learn that there are more real numbers than there are integers, but there are just as many pairs of integers as there are integers. In other words, infinity*infinity=infinity whilst 2^infinity>infinity The proofs are pretty easy, but that doesn't make the result less surprising to people who don't know it yet.
shoo 3y ago
Another example of this kind of thing is demonstrating that the set of rational numbers are countable. Each rational number has the form a / b for a pair of integers (a, b). This representation could be non-unique, e.g. 1/2 = -3/-6 are two different representations of the same rational number as fractions of integers. For this representation to be unique let's require the denominator b to be positive and a, b to have no common divisor. Let's consider (a, b) a point with integer coordinates on the lattice Z x Z, where Z is the set of integers (Z = { ..., -2, -1, 0, 1, 2, ... }). We can count each of these points if we begin by labeling the origin (0, 0) as "0" then (1, 0) as "1" then (0, 1) as "2",(-1, 0) as "3", etc. We can order these integer lattice points first by their increasing magnitude |a| + |b| from the origin and then by the angle they make relative to the origin and count them all one by one. Informally this shows that the set of rational numbers is not larger (in the sense of cardinality) as N_{>=0}, the set of non-negative integers. It's not smaller either as the set of non-negative integers N_{>=0} are a subset of rational numbers.

kybernetikos 3y ago

Factoradic is another interesting number system I've occasionally had reason to use. It's handy for counting permutations.

ithkuil 3y ago

Obligatory reference to Dimitri's Combo Class: https://youtu.be/GWA_NraxOUw https://youtu.be/GWA_NraxOUw https://youtu.be/hI-pwt7LyUw https://youtu.be/hI-pwt7LyUw https://youtu.be/MM0Sbfvf2Hw https://youtu.be/MM0Sbfvf2Hw

Out_of_Characte 3y ago

Stuff like this makes me feel like the base10 system might eventually get replaced by an even more usefull counting system.

cassepipe 3y ago
Does it not boil down to a tradeoff between the amount of symbols you are willing to learn and the space you want to use to write a number down ? Base 10 strikes me as good tradeoff
- Qem 3y ago
  Also a tradeoff with the size of the arithmetic tables one has to learn by rote. It scales with n^2. 100 entries in base 10, and just 36 in base 6, for example.
- avhon1 3y ago
  ...and also the number of integer factors of your base. 10 only has 1, 2, 5, and 10. Bases 8 and 6 have just as many. Bases 12 and 60 (used by the Sumerians and Babylonians) offer more convenient divisors.
Spivak 3y ago
Base 12! The operations humans do a lot divide by 2,3,4,12 can be done evenly. Your goal is to pack as many factors into your base as possible. They're called highly composite numbers and their big brother superior highly composite numbers. Base 10: 1,2,5,10 Base 12: 1,2,3,4,6,12 Base 60: 1,2,3,4,5,6,10,12,15,20,30,60 https://en.m.wikipedia.org/wiki/Superior_highly_composite_number https://en.m.wikipedia.org/wiki/Superior_highly_composite_nu...
- Qem 3y ago
  Children starting school would not be amused needing to learn 144 entries arithmetic tables. Lots of people were scarred already, starting with a lot of resentment against math due to sheer boredom of rote learning 100 entries tables close when they are first presented to the subject.

taeric 3y ago

Knuth's volume that goes over different number systems was a ton of fun. Goes over some of the interesting ideas behind such things as two's compliment numbers, as well. That is, even within the same base, you can have different ways of doing things. "Balanced ternary" is the one that seems like it had the most potential outside of binary, in a computer. That ship has firmly sailed, at this point.

sdenton4 3y ago

I'm a big fan of the Fibonacci base: https://en.m.wikipedia.org/wiki/Fibonacci_coding https://en.m.wikipedia.org/wiki/Fibonacci_coding It has the nice property that it's a) binary, and b) each number contains a '11' substring at the end, but nowhere else. This makes it slightly less efficient than the usual base 2 binary, but handles variable length integers nicely; you always know where one number ends and the next begins, so you don't have to worry about overflow or specifying the length of a number.