1
$\begingroup$

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_N$ returns the remainder of $n$ divided by $N$. I need the modulo of $n$ by $N$ because only the bottom $Q$ digits of $n$ are truncated. But I am struggling showing the following \begin{align} \mathbb{T}\left\{r^D n\right\} = \mathbb{T} \left\{r^D n + m\right\} \end{align} for $0 \leq m < r^D$ and $r^D +m > N$. Clearly this is true from my experience in computer science, but when I evaluate the expression for $r^D n+m$ mathematically, I get \begin{align} \mathbb{T}\left\{r^D n + m \right\} &= \frac{1}{r^{D}} \left[ \left_N - \left_M\right] \\ &= \frac{1}{r^D} \left[ \left_N - \left< \left_M + \left< m \right>_M \right>_M \right] \\ &= \frac{1}{r^D} \left[ \left< r^D n + m \right>_N - \left< m \right>_M \right]\\ &= \frac{1}{r^D} \left[ \left< r^D n + m \right>_N - m \right] \end{align} which in no way that I am familiar with readily simplifies to \begin{align} \mathbb{T} \left\{ r^D n \right\} = \frac{1}{r^D} \left[ \left< r^D n \right>_N \right] \end{align} I am sure that it does, but I might be missing some elementary modulo arithmetic tricks that other users of this site might readily have on hand.

  • 0
    Should 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 1

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.