Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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\right>_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<r^D n + m\right>_N - \left<r^D n + m \right>_M\right] \\ &= \frac{1}{r^D} \left[ \left<r^D n + m \right>_N - \left< \left<r^D n \right>_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.

share|improve this question
    
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. –  Ben Sep 22 '12 at 22:29
    
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. –  Gerry Myerson Sep 23 '12 at 23:56
    
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<r^D n + m\right>_N - \left<r^D n + m \right>_M = \left<r^D n \right>_N - \left<r^D n \right>_M$$ for all $n \in \mathbb{Z}$ and $m < r^D$. –  dcdo Sep 24 '12 at 0:41
    
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. –  dcdo Sep 24 '12 at 0:53
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.