4 ms·

I've seen people suggest using pi as a "database." In this instance you could map ranges of pi to characters. Then you search pi until you find the right range.

I've seen people suggest using pi as a "database." In this instance you could map ranges of pi to characters. Then you search pi until you find the right range. The URL would contain the range(s) needed. This is terrible and so computationally wasteful. But it's interesting to think about.

earthboundkid 6y ago
"X in pi" is an interesting thought experiment, but practically speaking, the least efficient way to do anything, since finding a string of N digits in pi will require a search space exponentially much larger than N on average, so it ends up just being an extremely inefficient encoding. A huffman coding + base32/base64 is a better "databaseless" short URL system.
skulk 6y ago
In a similar vein, almost every algorithm can be converted into a O(1) space version simply by converting it into the dumbest possible search algorithm over the solution space: just sample from the solution space randomly (with a seeded PRNG or something) until you get the right answer. A well-known example of this is bogosort: https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort
- teraflop 6y ago
  Interestingly, bogosort cannot actually be implemented in constant space -- at least, not if you're talking about a deterministic algorithm. In order for your PRNG to have a large enough state space to cover all possible permutations, it needs O(n log n) bits. In the Turing machine model of computation, algorithms that use O(1) space are theoretically equivalent to finite state machines (potentially with a very large number of states). Logarithmic space is where things start to get interesting, because it's enough to store a constant number of pointers into an arbitrarily large input.
fishtoaster 6y ago
Seems technically possible - example.com/12_3456 would calculate out pi, read 12 digits starting at position 3456, then convert those digits to ascii and you'd have your result. Given how far into the digits pi you'd have to go to find the exact right sequence that matches, eg, https://google.com https://google.com, though, I suspect the resulting position number would be longer than the original url! Also, conceptually, it seems like you're not so much using pi as a database as you are using it as an encoding mechanism: turning "abc.com" into a string of numbers whose length is relative to the original string. At that point you might as well pick an easier encoding, like base64. :)
- c22 6y ago
  You could add a short one or two character long identifier that changed the digits-of-pi to ascii map then select the mapping that results in the lowest index. In this case part of the "database" would exist within the URL shortener itself.
layoutIfNeeded 6y ago
On average the resulting URLs would be as long (or longer) as the original. You can’t cheat entropy.

earthboundkid 6y ago

"X in pi" is an interesting thought experiment, but practically speaking, the least efficient way to do anything, since finding a string of N digits in pi will require a search space exponentially much larger than N on average, so it ends up just being an extremely inefficient encoding. A huffman coding + base32/base64 is a better "databaseless" short URL system.

skulk 6y ago

In a similar vein, almost every algorithm can be converted into a O(1) space version simply by converting it into the dumbest possible search algorithm over the solution space: just sample from the solution space randomly (with a seeded PRNG or something) until you get the right answer. A well-known example of this is bogosort: https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort

teraflop 6y ago
Interestingly, bogosort cannot actually be implemented in constant space -- at least, not if you're talking about a deterministic algorithm. In order for your PRNG to have a large enough state space to cover all possible permutations, it needs O(n log n) bits. In the Turing machine model of computation, algorithms that use O(1) space are theoretically equivalent to finite state machines (potentially with a very large number of states). Logarithmic space is where things start to get interesting, because it's enough to store a constant number of pointers into an arbitrarily large input.

fishtoaster 6y ago

Seems technically possible - example.com/12_3456 would calculate out pi, read 12 digits starting at position 3456, then convert those digits to ascii and you'd have your result. Given how far into the digits pi you'd have to go to find the exact right sequence that matches, eg, https://google.com https://google.com, though, I suspect the resulting position number would be longer than the original url! Also, conceptually, it seems like you're not so much using pi as a database as you are using it as an encoding mechanism: turning "abc.com" into a string of numbers whose length is relative to the original string. At that point you might as well pick an easier encoding, like base64. :)

c22 6y ago
You could add a short one or two character long identifier that changed the digits-of-pi to ascii map then select the mapping that results in the lowest index. In this case part of the "database" would exist within the URL shortener itself.

layoutIfNeeded 6y ago

On average the resulting URLs would be as long (or longer) as the original. You can’t cheat entropy.