How do I make a primitive recursive function that does division?












3












$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))))









share|cite|improve this question











$endgroup$

















    3












    $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))))









    share|cite|improve this question











    $endgroup$















      3












      3








      3





      $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))))









      share|cite|improve this question











      $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






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      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






















          3 Answers
          3






          active

          oldest

          votes


















          1












          $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*}






          share|cite|improve this answer











          $endgroup$





















            0












            $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!!






            share|cite|improve this answer









            $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



















            0












            $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)))$$






            share|cite|improve this answer











            $endgroup$













              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
              });


              }
              });














              draft saved

              draft discarded


















              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









              1












              $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*}






              share|cite|improve this answer











              $endgroup$


















                1












                $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*}






                share|cite|improve this answer











                $endgroup$
















                  1












                  1








                  1





                  $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*}






                  share|cite|improve this answer











                  $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*}







                  share|cite|improve this answer














                  share|cite|improve this answer



                  share|cite|improve this answer








                  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























                      0












                      $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!!






                      share|cite|improve this answer









                      $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
















                      0












                      $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!!






                      share|cite|improve this answer









                      $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














                      0












                      0








                      0





                      $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!!






                      share|cite|improve this answer









                      $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!!







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      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


















                      • $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











                      0












                      $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)))$$






                      share|cite|improve this answer











                      $endgroup$


















                        0












                        $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)))$$






                        share|cite|improve this answer











                        $endgroup$
















                          0












                          0








                          0





                          $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)))$$






                          share|cite|improve this answer











                          $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)))$$







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited Jan 28 at 11:04









                          E.Nole

                          199114




                          199114










                          answered May 25 '17 at 9:15









                          HakaishinHakaishin

                          1166




                          1166






























                              draft saved

                              draft discarded




















































                              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.




                              draft saved


                              draft discarded














                              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





















































                              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







                              Popular posts from this blog

                              MongoDB - Not Authorized To Execute Command

                              in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith

                              How to fix TextFormField cause rebuild widget in Flutter