I wanted to find a mathematical expression to represent the truncation of the least $D$ digits of a number with radix $r$ without using the "floor" operation. So a $Q$-digit number written as $r_{Q-1}r_{Q-2}\ldots r_0$ should become $r_{Q-1}r_{Q-2}\ldots r_{D}$ after truncation. I think I came up with a satisfactory expression for my research for the truncated value of a number $n$ in a certain system \begin{align} \mathbb{T}\left\{n\right\} = \frac{1}{r^D} \left[ \left< n \right>_{N} - \left< n \right>_M \right] \end{align} where $N = r^Q$ and $M = r^D$ and $\left
Mathematical model for truncation of digits.
1
$\begingroup$
elementary-number-theory
discrete-mathematics
-
0One naive approach: convert your number to binary number n; define new binary number m s.t. m = {1}^(L-D)||{0}^(D) where L = len(n) and D is the number of digits you want truncated; perform bitwise AND on n and m; convert the result to base 10. – 2012-09-22
-
0It's clear from the set-up that $Q\gt D$. If $m\lt r^D$, then $r^D+m\lt2r^D\le r^{D+1}\le r^Q=N$, so the situation you are worried about never arises. – 2012-09-23
-
0I think my core question could have been more clearly stated without the extra text about why the problem arose in the first place. My core issue is trying to understand how to manipulate the modulo arithmetic to show that $$\left
_N - \left for all $n \in \mathbb{Z}$ and $m < r^D$. – 2012-09-24_M = \left _N - \left _M$$ -
0Should I modify the question to be more concise and clear or just add comments that clarify what I intended to ask versus what I actually asked? I am still new to the site. – 2012-09-24
1 Answers
0
Just working with the question in the comments, note that since $r^D=M$ and $0\le m\lt r^D$ we have $r^Dn$ reduced modulo $M$ is zero, and $m$ reduced modulo $M$ is $m$. So we are left with trying to prove that $r^Dn+m$ reduced modulo $N$ and $r^Dn$ reduced modulo $N$ differ by $m$. So write $r^Dn=Nq+t$ with $0\le t\lt N$. Note $t=r^Ds$ for some $s\lt r^{Q-D}$. Then $r^Dn+m=Nq+u$ where $$u=t+m\lt r^Ds+r^D=r^D(s+1)\le r^Q=N$$ so $r^Dn+m$ reduced modulo $N$ is $t+m$, as desired.