How do I make a primitive recursive function that does division?
$begingroup$
I am trying to define a primitive recursive function that does division. I looked at this answer but it seems wrong to me, because according to Wikipedia:
The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers
So the inequality x−t⋅y≥0 will always be true and the function will always keep adding +1. The function given in the answers seems right but only assuming that I have negative numbers. Now how could I build a PRF with just natural numbers?
EDIT: I found a way to either make a division that always rounds up or always rounds down. But I haven't found one yet that always does the correct thing. So far:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,S(m)))))
where S(m) is successor, A is addition, V is 0 if 0 and 1 otherwise, D is subtraction and M is multiplication.
Now the above always rounds down and the next one always rounds up:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,m))))
functions
$endgroup$
add a comment |
$begingroup$
I am trying to define a primitive recursive function that does division. I looked at this answer but it seems wrong to me, because according to Wikipedia:
The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers
So the inequality x−t⋅y≥0 will always be true and the function will always keep adding +1. The function given in the answers seems right but only assuming that I have negative numbers. Now how could I build a PRF with just natural numbers?
EDIT: I found a way to either make a division that always rounds up or always rounds down. But I haven't found one yet that always does the correct thing. So far:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,S(m)))))
where S(m) is successor, A is addition, V is 0 if 0 and 1 otherwise, D is subtraction and M is multiplication.
Now the above always rounds down and the next one always rounds up:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,m))))
functions
$endgroup$
add a comment |
$begingroup$
I am trying to define a primitive recursive function that does division. I looked at this answer but it seems wrong to me, because according to Wikipedia:
The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers
So the inequality x−t⋅y≥0 will always be true and the function will always keep adding +1. The function given in the answers seems right but only assuming that I have negative numbers. Now how could I build a PRF with just natural numbers?
EDIT: I found a way to either make a division that always rounds up or always rounds down. But I haven't found one yet that always does the correct thing. So far:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,S(m)))))
where S(m) is successor, A is addition, V is 0 if 0 and 1 otherwise, D is subtraction and M is multiplication.
Now the above always rounds down and the next one always rounds up:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,m))))
functions
$endgroup$
I am trying to define a primitive recursive function that does division. I looked at this answer but it seems wrong to me, because according to Wikipedia:
The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers
So the inequality x−t⋅y≥0 will always be true and the function will always keep adding +1. The function given in the answers seems right but only assuming that I have negative numbers. Now how could I build a PRF with just natural numbers?
EDIT: I found a way to either make a division that always rounds up or always rounds down. But I haven't found one yet that always does the correct thing. So far:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,S(m)))))
where S(m) is successor, A is addition, V is 0 if 0 and 1 otherwise, D is subtraction and M is multiplication.
Now the above always rounds down and the next one always rounds up:
Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,m))))
functions
functions
edited Nov 10 '17 at 5:27
J. M. is not a mathematician
61.5k5152290
61.5k5152290
asked May 21 '17 at 8:52


HakaishinHakaishin
1166
1166
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Definition by cases is a valid, derived principle of definition for primitive recursive functions. So is subtraction, and so is equality. I will therefore use them freely.
Moreover, it is a good idea to define not just integer division $d(m,n)$ but also the remainder function $r(m,n)$. One can then write
begin{align}
r(0,n) & = 0 \
r(m+1,n) & = begin{cases} 0 & text{if}; n-1 = r(m,n) \ r(m,n) + 1 &text{otherwise} end{cases}
end{align}
and define integer division by
begin{align*}
d(0,n) & = 0 \
d(m+1,n) & = begin{cases} d(m,n) + 1 & text{if}; r(m,n) = n-1 \
d(m,n) & text{otherwise} end{cases}
end{align*}
$endgroup$
add a comment |
$begingroup$
If y has to divide x such that x>y,
then, initially assuming i=0;
x/y=f(x,y,0);
f(x,y,i)=f(x-y,y,i+1)
quotient =i and remainder =x-y (finally, such that when
y>(x-y)) ,
the recursive step has to be stopped.
Example 1:
25/4=f(25,4,0)
=f(21,4,1)
=f(17,4,2)
=f(13,4,3)
=f(9,4,4)
=f(5,4,5)
=f(1,4,6)
Hence quotient=i=6 and reaminder=x-y=1.
i.e, 25=6*4+1!
Example 2:
30/8=f(30,8,0)
=f(22,8,1)
=f(14,8,2)
=f(6,8,3)
Since 6<8, we stop here.
Therefore 30=3*8+6!!
$endgroup$
$begingroup$
I am not sure this really answers my question. I know how to divide recursively. But I want to define a primitive recursive function with the form A(x,y,0) = something and A(x,y,i+1) = something depending on A
$endgroup$
– Hakaishin
May 21 '17 at 10:42
add a comment |
$begingroup$
I found a solution to my problem. The main issue was to figure out if $a - b geq 0.$ One has to use a little trick to figure this out. Below is the function I used for it and the final primitive recursive function that does division.
$a-b geq 0$
$BOE(a,0) = 1$
$BOE(a,S(m)) = A(V(D(a,S(m))),E(a,S(m)))$
with $A$ being Addition, $V(0) = 0$ else $1$, $D$ being subtraction, $E$ being equals, $S$ being successor and $M$ being multiplication.
$$ Div(x,y,0) = 0$$
$$Div(x,y,S(m)) = A(A(Div(x,y,m),V(D(x,M(y,S(m))))),E(D(x,M(m,y)),D(M(m,y),x)))$$
$endgroup$
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%2f2290137%2fhow-do-i-make-a-primitive-recursive-function-that-does-division%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Definition by cases is a valid, derived principle of definition for primitive recursive functions. So is subtraction, and so is equality. I will therefore use them freely.
Moreover, it is a good idea to define not just integer division $d(m,n)$ but also the remainder function $r(m,n)$. One can then write
begin{align}
r(0,n) & = 0 \
r(m+1,n) & = begin{cases} 0 & text{if}; n-1 = r(m,n) \ r(m,n) + 1 &text{otherwise} end{cases}
end{align}
and define integer division by
begin{align*}
d(0,n) & = 0 \
d(m+1,n) & = begin{cases} d(m,n) + 1 & text{if}; r(m,n) = n-1 \
d(m,n) & text{otherwise} end{cases}
end{align*}
$endgroup$
add a comment |
$begingroup$
Definition by cases is a valid, derived principle of definition for primitive recursive functions. So is subtraction, and so is equality. I will therefore use them freely.
Moreover, it is a good idea to define not just integer division $d(m,n)$ but also the remainder function $r(m,n)$. One can then write
begin{align}
r(0,n) & = 0 \
r(m+1,n) & = begin{cases} 0 & text{if}; n-1 = r(m,n) \ r(m,n) + 1 &text{otherwise} end{cases}
end{align}
and define integer division by
begin{align*}
d(0,n) & = 0 \
d(m+1,n) & = begin{cases} d(m,n) + 1 & text{if}; r(m,n) = n-1 \
d(m,n) & text{otherwise} end{cases}
end{align*}
$endgroup$
add a comment |
$begingroup$
Definition by cases is a valid, derived principle of definition for primitive recursive functions. So is subtraction, and so is equality. I will therefore use them freely.
Moreover, it is a good idea to define not just integer division $d(m,n)$ but also the remainder function $r(m,n)$. One can then write
begin{align}
r(0,n) & = 0 \
r(m+1,n) & = begin{cases} 0 & text{if}; n-1 = r(m,n) \ r(m,n) + 1 &text{otherwise} end{cases}
end{align}
and define integer division by
begin{align*}
d(0,n) & = 0 \
d(m+1,n) & = begin{cases} d(m,n) + 1 & text{if}; r(m,n) = n-1 \
d(m,n) & text{otherwise} end{cases}
end{align*}
$endgroup$
Definition by cases is a valid, derived principle of definition for primitive recursive functions. So is subtraction, and so is equality. I will therefore use them freely.
Moreover, it is a good idea to define not just integer division $d(m,n)$ but also the remainder function $r(m,n)$. One can then write
begin{align}
r(0,n) & = 0 \
r(m+1,n) & = begin{cases} 0 & text{if}; n-1 = r(m,n) \ r(m,n) + 1 &text{otherwise} end{cases}
end{align}
and define integer division by
begin{align*}
d(0,n) & = 0 \
d(m+1,n) & = begin{cases} d(m,n) + 1 & text{if}; r(m,n) = n-1 \
d(m,n) & text{otherwise} end{cases}
end{align*}
edited Apr 1 '18 at 9:04
Community♦
1
1
answered May 25 '17 at 12:07


Hans HüttelHans Hüttel
3,3572921
3,3572921
add a comment |
add a comment |
$begingroup$
If y has to divide x such that x>y,
then, initially assuming i=0;
x/y=f(x,y,0);
f(x,y,i)=f(x-y,y,i+1)
quotient =i and remainder =x-y (finally, such that when
y>(x-y)) ,
the recursive step has to be stopped.
Example 1:
25/4=f(25,4,0)
=f(21,4,1)
=f(17,4,2)
=f(13,4,3)
=f(9,4,4)
=f(5,4,5)
=f(1,4,6)
Hence quotient=i=6 and reaminder=x-y=1.
i.e, 25=6*4+1!
Example 2:
30/8=f(30,8,0)
=f(22,8,1)
=f(14,8,2)
=f(6,8,3)
Since 6<8, we stop here.
Therefore 30=3*8+6!!
$endgroup$
$begingroup$
I am not sure this really answers my question. I know how to divide recursively. But I want to define a primitive recursive function with the form A(x,y,0) = something and A(x,y,i+1) = something depending on A
$endgroup$
– Hakaishin
May 21 '17 at 10:42
add a comment |
$begingroup$
If y has to divide x such that x>y,
then, initially assuming i=0;
x/y=f(x,y,0);
f(x,y,i)=f(x-y,y,i+1)
quotient =i and remainder =x-y (finally, such that when
y>(x-y)) ,
the recursive step has to be stopped.
Example 1:
25/4=f(25,4,0)
=f(21,4,1)
=f(17,4,2)
=f(13,4,3)
=f(9,4,4)
=f(5,4,5)
=f(1,4,6)
Hence quotient=i=6 and reaminder=x-y=1.
i.e, 25=6*4+1!
Example 2:
30/8=f(30,8,0)
=f(22,8,1)
=f(14,8,2)
=f(6,8,3)
Since 6<8, we stop here.
Therefore 30=3*8+6!!
$endgroup$
$begingroup$
I am not sure this really answers my question. I know how to divide recursively. But I want to define a primitive recursive function with the form A(x,y,0) = something and A(x,y,i+1) = something depending on A
$endgroup$
– Hakaishin
May 21 '17 at 10:42
add a comment |
$begingroup$
If y has to divide x such that x>y,
then, initially assuming i=0;
x/y=f(x,y,0);
f(x,y,i)=f(x-y,y,i+1)
quotient =i and remainder =x-y (finally, such that when
y>(x-y)) ,
the recursive step has to be stopped.
Example 1:
25/4=f(25,4,0)
=f(21,4,1)
=f(17,4,2)
=f(13,4,3)
=f(9,4,4)
=f(5,4,5)
=f(1,4,6)
Hence quotient=i=6 and reaminder=x-y=1.
i.e, 25=6*4+1!
Example 2:
30/8=f(30,8,0)
=f(22,8,1)
=f(14,8,2)
=f(6,8,3)
Since 6<8, we stop here.
Therefore 30=3*8+6!!
$endgroup$
If y has to divide x such that x>y,
then, initially assuming i=0;
x/y=f(x,y,0);
f(x,y,i)=f(x-y,y,i+1)
quotient =i and remainder =x-y (finally, such that when
y>(x-y)) ,
the recursive step has to be stopped.
Example 1:
25/4=f(25,4,0)
=f(21,4,1)
=f(17,4,2)
=f(13,4,3)
=f(9,4,4)
=f(5,4,5)
=f(1,4,6)
Hence quotient=i=6 and reaminder=x-y=1.
i.e, 25=6*4+1!
Example 2:
30/8=f(30,8,0)
=f(22,8,1)
=f(14,8,2)
=f(6,8,3)
Since 6<8, we stop here.
Therefore 30=3*8+6!!
answered May 21 '17 at 10:15


BabuBabu
1116
1116
$begingroup$
I am not sure this really answers my question. I know how to divide recursively. But I want to define a primitive recursive function with the form A(x,y,0) = something and A(x,y,i+1) = something depending on A
$endgroup$
– Hakaishin
May 21 '17 at 10:42
add a comment |
$begingroup$
I am not sure this really answers my question. I know how to divide recursively. But I want to define a primitive recursive function with the form A(x,y,0) = something and A(x,y,i+1) = something depending on A
$endgroup$
– Hakaishin
May 21 '17 at 10:42
$begingroup$
I am not sure this really answers my question. I know how to divide recursively. But I want to define a primitive recursive function with the form A(x,y,0) = something and A(x,y,i+1) = something depending on A
$endgroup$
– Hakaishin
May 21 '17 at 10:42
$begingroup$
I am not sure this really answers my question. I know how to divide recursively. But I want to define a primitive recursive function with the form A(x,y,0) = something and A(x,y,i+1) = something depending on A
$endgroup$
– Hakaishin
May 21 '17 at 10:42
add a comment |
$begingroup$
I found a solution to my problem. The main issue was to figure out if $a - b geq 0.$ One has to use a little trick to figure this out. Below is the function I used for it and the final primitive recursive function that does division.
$a-b geq 0$
$BOE(a,0) = 1$
$BOE(a,S(m)) = A(V(D(a,S(m))),E(a,S(m)))$
with $A$ being Addition, $V(0) = 0$ else $1$, $D$ being subtraction, $E$ being equals, $S$ being successor and $M$ being multiplication.
$$ Div(x,y,0) = 0$$
$$Div(x,y,S(m)) = A(A(Div(x,y,m),V(D(x,M(y,S(m))))),E(D(x,M(m,y)),D(M(m,y),x)))$$
$endgroup$
add a comment |
$begingroup$
I found a solution to my problem. The main issue was to figure out if $a - b geq 0.$ One has to use a little trick to figure this out. Below is the function I used for it and the final primitive recursive function that does division.
$a-b geq 0$
$BOE(a,0) = 1$
$BOE(a,S(m)) = A(V(D(a,S(m))),E(a,S(m)))$
with $A$ being Addition, $V(0) = 0$ else $1$, $D$ being subtraction, $E$ being equals, $S$ being successor and $M$ being multiplication.
$$ Div(x,y,0) = 0$$
$$Div(x,y,S(m)) = A(A(Div(x,y,m),V(D(x,M(y,S(m))))),E(D(x,M(m,y)),D(M(m,y),x)))$$
$endgroup$
add a comment |
$begingroup$
I found a solution to my problem. The main issue was to figure out if $a - b geq 0.$ One has to use a little trick to figure this out. Below is the function I used for it and the final primitive recursive function that does division.
$a-b geq 0$
$BOE(a,0) = 1$
$BOE(a,S(m)) = A(V(D(a,S(m))),E(a,S(m)))$
with $A$ being Addition, $V(0) = 0$ else $1$, $D$ being subtraction, $E$ being equals, $S$ being successor and $M$ being multiplication.
$$ Div(x,y,0) = 0$$
$$Div(x,y,S(m)) = A(A(Div(x,y,m),V(D(x,M(y,S(m))))),E(D(x,M(m,y)),D(M(m,y),x)))$$
$endgroup$
I found a solution to my problem. The main issue was to figure out if $a - b geq 0.$ One has to use a little trick to figure this out. Below is the function I used for it and the final primitive recursive function that does division.
$a-b geq 0$
$BOE(a,0) = 1$
$BOE(a,S(m)) = A(V(D(a,S(m))),E(a,S(m)))$
with $A$ being Addition, $V(0) = 0$ else $1$, $D$ being subtraction, $E$ being equals, $S$ being successor and $M$ being multiplication.
$$ Div(x,y,0) = 0$$
$$Div(x,y,S(m)) = A(A(Div(x,y,m),V(D(x,M(y,S(m))))),E(D(x,M(m,y)),D(M(m,y),x)))$$
edited Jan 28 at 11:04
E.Nole
199114
199114
answered May 25 '17 at 9:15


HakaishinHakaishin
1166
1166
add a comment |
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%2f2290137%2fhow-do-i-make-a-primitive-recursive-function-that-does-division%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