Division without using '/' operator

Question

I cannot use '/' and loops and I have to divide some numbers. operands are 32-bit and I can't use recursion.

I thought of using shr but it only gives me 2^n divison and it also won't save the reminder.

any Ideas?

Division is just repeated subtraction. Why can't you use the divide operator? — i_am_jorf, May 08 '17 at 18:14
Perhaps some more specifics would help. What kind of datatypes can we assume need to be divided? uint32_t? int64_t? — AndyG, May 08 '17 at 18:16
I cant use the divide operator because im working on closed system with limited memory. Recursion is off the table. The number is uint32. C language. — Dorni, May 08 '17 at 18:20
@Domi any workaround is likely to take more memory than the regular divide operator ??! — AlexG, May 08 '17 at 18:21
@AlexG That's for sure... sounds like a made-up requirement or excuse... — Eugene Sh., May 08 '17 at 18:22
@Dorni: in that case you can just use the [magic number method](http://www.hackersdelight.org/magic.htm), which requires only multiplication, addition and shift. Please hit the [edit] button and add all the relevant info from comments into your question, as people are getting frustrated by its vagueness. — Paul R, May 08 '17 at 18:31
Related question (possible duplicate): [Perform integer division using multiplication](http://stackoverflow.com/q/30790184/253056). — Paul R, May 08 '17 at 18:35
I consulted Mr Occam and he said its a badly-disguised homework question with artificial contraints applied by prof/TA. — ThingyWotsit, May 08 '17 at 18:53
Resembles https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem — MBo, May 09 '17 at 03:10

score 1 · Answer 1 · answered May 08 '17 at 18:36

#include <stdio.h>
#include <stdlib.h>

int main()
{
   div_t output;

   output = div(27, 4);
   printf("Quotient part of (27/ 4) = %d\n", output.quot);
   printf("Remainder part of (27/4) = %d\n", output.rem);

   output = div(27, 3);
   printf("Quotient part of (27/ 3) = %d\n", output.quot);
   printf("Remainder part of (27/3) = %d\n", output.rem);

   return(0);
}

Output:

Quotient part of (27/ 4) = 6
Remainder part of (27/4) = 3
Quotient part of (27/ 3) = 9
Remainder part of (27/3) = 0

Rama · Answer 2 · 2017-05-08T19:24:15.993

Try this method based on magic numbers:
I implemented it based on this link
It is usefull only with fixed divisor.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    // your code goes here

    unsigned long MAX_NUM=1<<30; //Max num = 1073741824

    unsigned long num = 1073741824;
    unsigned long divisor=17;

    //unsigned long magic_num=round(double(MAX_NUM)/divisor);
    unsigned long magic_num = 63161284 // Fixed for divisor = 17

    unsigned long div = (num * magic_num) >> 30;
    unsigned long remain = num - div * divisor;

    cout << div << endl;
    cout << remain << endl;

    return 0;
}

score 0 · Answer 3 · edited May 08 '17 at 18:26

0

int a_div_b( int a, int b, int pow=0 ) {
  if (a<b) return 0;
  if (a < (b<<(pow+1)))
    return a_div_b(a-(b<<pow), b) + (1<<pow);
  return a_div_b(a, b, pow+1);
}

No loops, no /, O((log(a/b))^2) time. I could probably improve to O(log(a/b)), but I am lazy (recurse down from maximium pow once you find it, not back up).

Remainder can be easily calculated via b-a_div_b(a,b)*a without use of loops or /.

It should use O(1) memory as it is tail-end-recursive.

edited May 08 '17 at 18:26

Paul R

208,748
37
389
560

answered May 08 '17 at 18:21

Yakk - Adam Nevraumont

262,606
27
330
524

1

Good answer, but OP says in comments: "Recursion is off the table", which I take to mean "recursion is not allowed". – Paul R May 08 '17 at 18:23
1

@PaulR I'm glad the OP has a different question. He can press the "Ask Question" button to ask it. – Yakk - Adam Nevraumont May 08 '17 at 18:23
2

Yes, the goalposts are moving pretty fast on this question! – Paul R May 08 '17 at 18:24
I would say just unroll this for 32-bit unsigned values. – Khouri Giordano May 08 '17 at 18:29
I think recursion will use a lot of memory with large numbers so i'm not supposed to use it. – Dorni May 08 '17 at 18:30
1

@Dorni No, this uses O(1) memory assuming your compiler is not brain dead; it is tail-end recursive. – Yakk - Adam Nevraumont May 08 '17 at 18:37

score 0 · Answer 4 · answered May 08 '17 at 18:26

0

If this is an academic exercise, they are probably wanting you to do:

a/b ::== e**(log(a) - log(b))

answered May 08 '17 at 18:26

user3344003

20,574
3
26
62

OP claims this is for a resource-constrained system, apparently, so transcendental functions are probably going to be off-limits, I imagine. – Paul R May 08 '17 at 18:27
1

And he want it with remainder. But I would rather close the question as unclear with such a requirements which do not align. – Eugene Sh. May 08 '17 at 18:27
1

it seems like we are getting into impossibility now here. – user3344003 May 08 '17 at 18:29

Division without using '/' operator

4 Answers4