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
    One 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
  • 0
    It'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
  • 0
    I 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_M = \left_N - \left_M$$ for all $n \in \mathbb{Z}$ and $m < r^D$.2012-09-24
  • 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.