15
votes
Algorithm to convert a fixed-length string to the smallest possible collision-free representation?
As ratchet freak says, you have ten decimal digits, which should give $10^{10}$ possible values. But in practice, there are a few more restrictions. The format of a North American telephone number ...
- 7,176
11
votes
Algorithm to convert a fixed-length string to the smallest possible collision-free representation?
You have 10 base10 digits. This is $10^{10}$ possible values.
Encoding this in an alphabet with 64 tokens you need $\lceil \log_{64}(10^{10}) \rceil = 6$ characters.
If you encode it in straight ...
- 4,646
4
votes
Accepted
Streaming digit-to-digit conversion from decimal to hexadecimal
I don't think this is possible. Changing a high-order digit in a base-10 number -- say, changing 5000000 to 6000000 -- can change bits in its binary equivalent all the way from high-order bits to ...
- 5,489
4
votes
Accepted
Base transcoding with minimum storage and complexity
Divide the first 187 bits into 17 blocks of 11-bit values. This leaves 5 bits left over. Call each 11-bit block good if it it corresponds to a number in the range $0 \ldots 2024$, or bad if it is in ...
D.W.♦
- 164k
3
votes
Accepted
Convert a decimal floating-point number into a binary floating-point number
I am not an expert in this area, but the following is what I know about this problem. This problem was solved in the following paper:
William D. Clinger. How to read floating point numbers accurately,...
- 289
2
votes
Find n-th number in a number system with only 3 and 4
You're on the right track, it is similar to binary in a way.
The first step to coming up with an efficient solution is to recognize that to convert a number from the $3,4$ system to decimal, you can ...
- 121
2
votes
Time complexity of expanding decimal to new base
Let me start with a short introduction on computation models. A (C-like) computation model specifies the inventory of operations, and the cost of each operation. Two popular computation models are the ...
- 278k
2
votes
Accepted
Optimal way for the remainder
You would pick some number a, run the code, and see if you can find a pattern. There will be an obvious pattern. Then you think how you can use that pattern to find long ranges of numbers i where r ...
- 31.4k
2
votes
Accepted
How does Decimal to Binary conversion algorithm work?
No, you have not done anything wrong.
However, you have not done enough. You have done step 2 for 18 times. You will have to repeat step 2 for another 82 times. Then you will observe that the "...
- 39k
2
votes
Streaming digit-to-digit conversion from decimal to hexadecimal
You can't do this - if you don't know whether the input is k digits or k+1 digits, then the additional decimal digit changes all or most of the hexadecimal digits. For example 100 -> 64, but 1000 -> ...
- 31.4k
2
votes
Accepted
Conversion from octal numerical system to binary numerical system
Its not a coincidence. It is a general result for any number represented in a positive base $b$, its representation in base $b^k$ for some positive integer $k$, is simply grouping $k$ digits in its ...
2
votes
Algorithm to convert a fixed-length string to the smallest possible collision-free representation?
Draconis already gave an excellent answer of the specific theoretical limitations of your question. However, I figured it wouldn't hurt to show an explicit implementation of such an encoding schema.
...
1
vote
Accepted
Are leading zeros necessary when referring to other bases in certain contexts?
The grading standards of your course are up to your instructor, and it's not the purpose of this site to take a position on grades.
That said, based on what is presented here, my personal view is that ...
D.W.♦
- 164k
1
vote
Fast string-to-integer algorithm
I'm adding an answer to share my rough JavaScript version of V8's FromStringLarge algorithm:
...
- 123
1
vote
Why does the hash function in Rabin—Karp produce unique hashes?
What is the basis for using this function which looks like we're converting to a number system - does that guarantee uniqueness?
No, it's not possible to guarantee uniqueness if H is of a fixed size ...
- 339
1
vote
algorithm to check the existence of $b-1$ in $(n)_b$?
The fastest way is likely going to be to compute the base-$b$ representation of $n$, and then scan over it to see whether it contains the desired digit. That is a linear-time algorithm.
Solving a ...
D.W.♦
- 164k
1
vote
Accepted
Arithmetic on signed 12-bit octal number stored in sign magnitude form
$100 011 110 101$ if is taken as SM in 12bit is $-245$ decimal and $011 100 001 010$ is $1802$ decimal, so we obtain $-245-1802=-2047$. $2047$ in binary is $11111111111$ with $11$ bits so for minus ...
- 2,364
1
vote
Why is the carry of any n base system equal to the radix in arithmetic?
Background
Writing a number in base $r$ means to write it in the form
$$a_0+a_1r+a_2r^2+\ldots+a_nr^n$$
where $0\leq a_i< r$, for all $i=0,1,\ldots,n$. The positional notation that we use consists ...
- 1,189
1
vote
Accepted
Conversion of fractional part of a hexadecimal number to binary
Here is how to convert the fractional part from hexadecimal to binary:
$$
(0.25)_{16} = \frac{2}{16} + \frac{5}{16^2} =
\frac{0 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1}{16} +
\frac{0 \cdot 8 + 1 \...
- 278k
1
vote
Writing a Turing Machine that convers a number from binary to decimal
Since you don't have any questions in your post, it's hard to give any concrete tips.
Try to do the simpler binary to unary converter instead. And should also assume that you have as many working ...
- 16.7k
1
vote
Newbie: hexadecimal editors to make sense of binary files
20 02 00 00 26 53 53 42 89 b2 e5 c2 71 3d 76 41
Full answer is impossible in your case, instead I'm giving clarifications.
We should know the data format to convert binary file to human readable ...
- 170
1
vote
Accepted
4-digit 5's complement of a negative number
Let me demystify $b$'s complement.
Let $b \geq 2$ be an integer. Given a $d$-digit integer $x$ is base $b$, we want to find a $d$-digit integer $y$ such that $y \equiv -x \pmod{b^d}$. Why is this ...
- 278k
1
vote
Accepted
How to convert between bases partially?
Partial answer:
It works for some pairs $b_1$ $b_2$, but may not work for every pair.
Partial solution:
for pairs $b_1$ $b_2$ where there is an $x, p_1, p_2 \in \mathbb{Z}$ such that
$\begin{...
- 241
1
vote
Is there an online algorithm for radix conversion?
This answer is not complete, but it is the start of a complete answer, and nothing else has been offered. I hope to finish it another time.
I have found that an online right-to-left algorithm exists ...
- 1,537
1
vote
Shortest decimal expansion within binary interval
Decimal numbers with k digits to the right of the decimal point are $10^{-k}$ apart. So if you choose k large enough that $10^{-k} < 2·2^n$, then there is a decimal number with k decimals inside ...
- 31.4k
Only top scored, non community-wiki answers of a minimum length are eligible