How to shift right in modular arithmetic $2^n$ using only subtraction and multiplication.
$begingroup$
In modular arithmetic $2^n$ it is easy to shift left number $x$ by doing $(xll 1)=2x=x+x=x-(0-x)$. Shifting right on the other hand is integer division by the power of 2, e.g. $(xgg 1)=lfloor x/2 rfloor$. My question: Is it possible to shift right using only addition, subtraction and multiplication?
I suspect it is not possible.
I do not have direct access to the bits of the number. I know that the operation $(xll (n-1)) pmod{2^{n+1}}$ effectively gives $(xgg 1)$ in the upper half of the bit array. This trick is not good since it requires erasing the lower half, which is not addition/subtraction/multiplication.
By squaring the number a few times it is possible to calculate $(x&1)=x%2=(x pmod 2)$, because all odd numbers give $1$ and all even give $0$. This is erasing all higher bits except the lowest. But erasing lower bits leaving the higher is also questionable.
modular-arithmetic bit-strings
asked Dec 21 '18 at 5:47
oddyoddy
184
$endgroup$
add a comment |
$begingroup$
In modular arithmetic $2^n$ it is easy to shift left number $x$ by doing $(xll 1)=2x=x+x=x-(0-x)$. Shifting right on the other hand is integer division by the power of 2, e.g. $(xgg 1)=lfloor x/2 rfloor$. My question: Is it possible to shift right using only addition, subtraction and multiplication?
I suspect it is not possible.
I do not have direct access to the bits of the number. I know that the operation $(xll (n-1)) pmod{2^{n+1}}$ effectively gives $(xgg 1)$ in the upper half of the bit array. This trick is not good since it requires erasing the lower half, which is not addition/subtraction/multiplication.
By squaring the number a few times it is possible to calculate $(x&1)=x%2=(x pmod 2)$, because all odd numbers give $1$ and all even give $0$. This is erasing all higher bits except the lowest. But erasing lower bits leaving the higher is also questionable.
modular-arithmetic bit-strings
asked Dec 21 '18 at 5:47
oddyoddy
184
$endgroup$
4
$begingroup$
You should explain what a shift is since not everyone here has a programming background.
$endgroup$
– Toby Mak
Dec 21 '18 at 5:55
$begingroup$
You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$
$endgroup$
– gammatester
Dec 21 '18 at 9:11
$begingroup$
Thanks, edited accordingly.
$endgroup$
– oddy
Dec 22 '18 at 6:36
add a comment |
$begingroup$
In modular arithmetic $2^n$ it is easy to shift left number $x$ by doing $(xll 1)=2x=x+x=x-(0-x)$. Shifting right on the other hand is integer division by the power of 2, e.g. $(xgg 1)=lfloor x/2 rfloor$. My question: Is it possible to shift right using only addition, subtraction and multiplication?
I suspect it is not possible.
I do not have direct access to the bits of the number. I know that the operation $(xll (n-1)) pmod{2^{n+1}}$ effectively gives $(xgg 1)$ in the upper half of the bit array. This trick is not good since it requires erasing the lower half, which is not addition/subtraction/multiplication.
By squaring the number a few times it is possible to calculate $(x&1)=x%2=(x pmod 2)$, because all odd numbers give $1$ and all even give $0$. This is erasing all higher bits except the lowest. But erasing lower bits leaving the higher is also questionable.
modular-arithmetic bit-strings
asked Dec 21 '18 at 5:47
oddyoddy
184
$endgroup$
In modular arithmetic $2^n$ it is easy to shift left number $x$ by doing $(xll 1)=2x=x+x=x-(0-x)$. Shifting right on the other hand is integer division by the power of 2, e.g. $(xgg 1)=lfloor x/2 rfloor$. My question: Is it possible to shift right using only addition, subtraction and multiplication?
I suspect it is not possible.
I do not have direct access to the bits of the number. I know that the operation $(xll (n-1)) pmod{2^{n+1}}$ effectively gives $(xgg 1)$ in the upper half of the bit array. This trick is not good since it requires erasing the lower half, which is not addition/subtraction/multiplication.
By squaring the number a few times it is possible to calculate $(x&1)=x%2=(x pmod 2)$, because all odd numbers give $1$ and all even give $0$. This is erasing all higher bits except the lowest. But erasing lower bits leaving the higher is also questionable.
modular-arithmetic bit-strings
modular-arithmetic bit-strings
asked Dec 21 '18 at 5:47
oddyoddy
184
asked Dec 21 '18 at 5:47
oddyoddy
184
edited Dec 22 '18 at 7:08
oddy
asked Dec 21 '18 at 5:47
oddyoddy
184
asked Dec 21 '18 at 5:47
oddyoddy
184
asked Dec 21 '18 at 5:47
oddyoddy
184
184
4
$begingroup$
You should explain what a shift is since not everyone here has a programming background.
$endgroup$
– Toby Mak
Dec 21 '18 at 5:55
$begingroup$
You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$
$endgroup$
– gammatester
Dec 21 '18 at 9:11
$begingroup$
Thanks, edited accordingly.
$endgroup$
– oddy
Dec 22 '18 at 6:36
add a comment |
4
$begingroup$
You should explain what a shift is since not everyone here has a programming background.
$endgroup$
– Toby Mak
Dec 21 '18 at 5:55
$begingroup$
You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$
$endgroup$
– gammatester
Dec 21 '18 at 9:11
$begingroup$
Thanks, edited accordingly.
$endgroup$
– oddy
Dec 22 '18 at 6:36
4
4
$begingroup$
You should explain what a shift is since not everyone here has a programming background.
$endgroup$
– Toby Mak
Dec 21 '18 at 5:55
$begingroup$
You should explain what a shift is since not everyone here has a programming background.
$endgroup$
– Toby Mak
Dec 21 '18 at 5:55
$begingroup$
You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$
$endgroup$
– gammatester
Dec 21 '18 at 9:11
$begingroup$
You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$
$endgroup$
– gammatester
Dec 21 '18 at 9:11
$begingroup$
Thanks, edited accordingly.
$endgroup$
– oddy
Dec 22 '18 at 6:36
$begingroup$
Thanks, edited accordingly.
$endgroup$
– oddy
Dec 22 '18 at 6:36
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
No, it's not possible for $ngeq 2$.
Suppose there is some polynomial $p(X) in (mathbb{Z}/2^n mathbb{Z}) [X]$ such that $p(a) = lfloor frac{a}{2}rfloor$ for all $ain mathbb{Z}/2^n mathbb{Z}$.
First, set $a=0$. Since $p(0) = 0$, the constant term of $p$ is $0$.
Next, set $a=2^{n-1}$. Since $(2^{n-1})^2 = 2^{2n-2}$ and $2n-2 geq n$, all the terms of $p(2^{n-1})$ are zero besides possibly the linear term. But $p(2^{n-1}) = 2^{n-2}$, while the linear term is divisible by $2^{n-1}$, contradiction.
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
$endgroup$
$begingroup$
Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1.
$endgroup$
– Peter Taylor
Dec 22 '18 at 8:08
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3048219%2fhow-to-shift-right-in-modular-arithmetic-2n-using-only-subtraction-and-multip%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No, it's not possible for $ngeq 2$.
Suppose there is some polynomial $p(X) in (mathbb{Z}/2^n mathbb{Z}) [X]$ such that $p(a) = lfloor frac{a}{2}rfloor$ for all $ain mathbb{Z}/2^n mathbb{Z}$.
First, set $a=0$. Since $p(0) = 0$, the constant term of $p$ is $0$.
Next, set $a=2^{n-1}$. Since $(2^{n-1})^2 = 2^{2n-2}$ and $2n-2 geq n$, all the terms of $p(2^{n-1})$ are zero besides possibly the linear term. But $p(2^{n-1}) = 2^{n-2}$, while the linear term is divisible by $2^{n-1}$, contradiction.
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
$endgroup$
$begingroup$
Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1.
$endgroup$
– Peter Taylor
Dec 22 '18 at 8:08
add a comment |
$begingroup$
No, it's not possible for $ngeq 2$.
Suppose there is some polynomial $p(X) in (mathbb{Z}/2^n mathbb{Z}) [X]$ such that $p(a) = lfloor frac{a}{2}rfloor$ for all $ain mathbb{Z}/2^n mathbb{Z}$.
First, set $a=0$. Since $p(0) = 0$, the constant term of $p$ is $0$.
Next, set $a=2^{n-1}$. Since $(2^{n-1})^2 = 2^{2n-2}$ and $2n-2 geq n$, all the terms of $p(2^{n-1})$ are zero besides possibly the linear term. But $p(2^{n-1}) = 2^{n-2}$, while the linear term is divisible by $2^{n-1}$, contradiction.
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
$endgroup$
$begingroup$
Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1.
$endgroup$
– Peter Taylor
Dec 22 '18 at 8:08
add a comment |
$begingroup$
No, it's not possible for $ngeq 2$.
Suppose there is some polynomial $p(X) in (mathbb{Z}/2^n mathbb{Z}) [X]$ such that $p(a) = lfloor frac{a}{2}rfloor$ for all $ain mathbb{Z}/2^n mathbb{Z}$.
First, set $a=0$. Since $p(0) = 0$, the constant term of $p$ is $0$.
Next, set $a=2^{n-1}$. Since $(2^{n-1})^2 = 2^{2n-2}$ and $2n-2 geq n$, all the terms of $p(2^{n-1})$ are zero besides possibly the linear term. But $p(2^{n-1}) = 2^{n-2}$, while the linear term is divisible by $2^{n-1}$, contradiction.
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
$endgroup$
No, it's not possible for $ngeq 2$.
Suppose there is some polynomial $p(X) in (mathbb{Z}/2^n mathbb{Z}) [X]$ such that $p(a) = lfloor frac{a}{2}rfloor$ for all $ain mathbb{Z}/2^n mathbb{Z}$.
First, set $a=0$. Since $p(0) = 0$, the constant term of $p$ is $0$.
Next, set $a=2^{n-1}$. Since $(2^{n-1})^2 = 2^{2n-2}$ and $2n-2 geq n$, all the terms of $p(2^{n-1})$ are zero besides possibly the linear term. But $p(2^{n-1}) = 2^{n-2}$, while the linear term is divisible by $2^{n-1}$, contradiction.
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
answered Dec 22 '18 at 6:52
SladeSlade
25.2k12665
25.2k12665
$begingroup$
Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1.
$endgroup$
– Peter Taylor
Dec 22 '18 at 8:08
add a comment |
$begingroup$
Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1.
$endgroup$
– Peter Taylor
Dec 22 '18 at 8:08
$begingroup$
Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1.
$endgroup$
– Peter Taylor
Dec 22 '18 at 8:08
$begingroup$
Alternatively you can show that $p(2)$ must be a multiple of 2 which equals 1.
$endgroup$
– Peter Taylor
Dec 22 '18 at 8:08
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3048219%2fhow-to-shift-right-in-modular-arithmetic-2n-using-only-subtraction-and-multip%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
$begingroup$
You should explain what a shift is since not everyone here has a programming background.
$endgroup$
– Toby Mak
Dec 21 '18 at 5:55
$begingroup$
You have a very unusual definition of shift right since $x<<1$ is normally considered to be a left shift. And instead of $x<< (2^n-1)$ you most probably mean $x<< (n-1)$ because your expression is zero for most $n!$
$endgroup$
– gammatester
Dec 21 '18 at 9:11
$begingroup$
Thanks, edited accordingly.
$endgroup$
– oddy
Dec 22 '18 at 6:36