division by 7 without using division operator

B

Ben Pfaff

Richard Heathfield said:
To give you a different example, if the interviewer asked you
what was wrong with this program:
[...]

how would you reply?

"From what point of view? I can do ISO 9899-1990, -1995, or -1999,
ISO 14882-1998, SUSv3, GNU, comp.lang.c, or clueless newbie."
 
R

Richard Heathfield

Richard Tobin said:
Nonetheless, I think my assumption is likely to be right. Obviously
the best thing to do would be to verify that assumption before
answering the question.

Actually, I'd give the answer I did give, along with weasel words such as
"well, this is the easiest, most obvious way", and then ask whether he had
expected a bit-twiddling answer. If so, I'd be prepared to give it,
obviously.
Just giving the answer you suggested does not seem like a good strategy.

I still think it's a perfectly valid answer. Had I asked the question with
bit-twiddling in mind, and then received that answer, I'd probably laugh
and say "er, oh yeah, good point - well, okay, how about a solution that
doesn't require any function calls?" (And I'd mentally award him a few
points for simplicity and creativity.) I once asked a candidate how he
would rotate an unsigned int. He wrote this:

unsigned int i = 42;

turned the piece of paper around (which I assumed was so that I could see
it), and sat back in an attitude of "okay, I'm ready for the next
question". It took me a moment to work it out, but I gave him 10/10 for
chutzpah and quick thinking. (And yes, then I asked the same question more
precisely, and yes, he came up with a good *technical* answer.)
"You aren't Richard Heathfield by any chance, are you?"


I would assume that the interviewer realised that there were several
errors of varying seriousness, and that he wanted me to list them. Of
course, I might be wrong, but such is life.

Most were obvious, of course, but there was a subtlety in there that I would
expect only an expert to spot. If the candidate saw that one, I would
consider the question to be correctly answered, even if he dismissed the
rest with "oh, and there's a bunch of other stuff wrong as well".
 
B

Ben Pfaff

Richard Heathfield said:
#include <stdio.h>
#include <stdlib.h>
#include <strlen.h>

No such standard header.
#include <assert.h>

main(int c, char **v)

Needs a return type, especially in C99.
It's kind to use the customary names argc and argv for the
arguments.
{
char *p = malloc(strlen(v[0]));

argc == 0 is permissible under the C standard, in which case
argv[0] is NULL, so this yields undefined behavior.
char *q, *r;
assert(p);

An assertion is not an appropriate way to check for failures that
can actually occur in practice.
strcpy(p, v[0]);

Didn't allocate enough memory for this.
q = p;
r = q + strlen(p) - 1;

If argv[0] == '\0', this attempts to back up past the beginning
of an allocated object, yielding undefined behavior.
while(q < r)
{
char c = *q; *q++ = *r; *r-- = c;
}

I'm not going to bother to analyze this. Likely problems include
stepping off the beginning or the end of the array.
puts(p);
}

Should return a value, probably 0 or EXIT_SUCCESS.
 
R

Richard Heathfield

Ben Pfaff said:
No such standard header.

This was actually a genuine typo, which I spotted and was about to correct
when I thought, blow it, why not leave it in? I should actually have fixed
it, on reflection, as it would have left the program in a compilable state
despite the errors, and that would have clued the candidate in to the fact
that this is supposed to be C90 code (see below).
Needs a return type, especially in C99.

Actually, that was a clue that this was C90, and this is relevant.

I'm not going to bother to analyze this. Likely problems include
stepping off the beginning or the end of the array.

Actually, had you bothered to analyse it, you would have found that it's
about the only part of the program that is actually correct. :)

Alas, you didn't spot the (admittedly C90-only, and there's a clue for you
if ever there was one) subtlety.
 
R

Richard Tobin

Richard Heathfield said:
Most were obvious, of course, but there was a subtlety in there that I would
expect only an expert to spot.

Go on, tell us. I assume it's that assert(pointer) is not allowed
(but works on all known systems).

-- Richard
 
M

micans

Pick your accuracy:

a: the required multiplication
b: the resulting factor from the operation

+ (a>>3)
a=0.142857 b=0.125 error=1.7857%

+ (a>>3) + (a>>6)
a=0.142857 b=0.140625 error=0.2232%

+ (a>>3) + (a>>6) + (a>>9)
a=0.142857 b=0.142578 error=0.0279%

+ (a>>3) + (a>>6) + (a>>9) + (a>>12)
a=0.142857 b=0.142822 error=0.0035%

<snip> progression

nice.

This uses the following relationship:

1/(1-x) = 1 + x + x**2 + x**3 + x**4 ... (continued; x < 1)

and the fact that 1/7 equals -1 + 1/(1-1/8), so x/7
equals x ( 1/8 + (1/8)**2 + (1/8)**3 ... )

Stijn
 
D

David T. Ashley

Richard Tobin said:
... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is
y * 0x500000001, which is congruent to y mod 2^32.

I suppose one of these days I should actually read the standards you guys
cite so often ...

but ...

naive question ...

does the standard actually guarantee that if you overflow a multiplication
you get the modulo 2^32 result?

All processors that I'm aware of work this way (in fact, on all processors
I'm aware of MUL is sized so that overflow is impossible), but it seems
somebody somewhere might have a processor with a 32 = 32 x 32 multiply and
if you overflow you get an overflow flag and an undefined result ... and if
this is the case it would be inconvenient to provide the modulo 2^32 result.

Is this guaranteed on a multiplication overflow?
 
B

Ben Pfaff

David T. Ashley said:
does the standard actually guarantee that if you overflow a multiplication
you get the modulo 2^32 result?

For an unsigned 32-bit type, yes.
For signed types, no.
 
R

Richard Tobin

David T. Ashley said:
does the standard actually guarantee that if you overflow a multiplication
you get the modulo 2^32 result?

We were assuming that unsigned ints are 32 bits, which is of course not
guaranteed, but arithmetic on unsigned ints *is* guaranteed to work
modulo 2^N, where N is the number of bits. For signed integers,
anything may happen.

-- Richard
 
K

Krypto

The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7
 
R

Richard Harter

<snip> progression

nice.

This uses the following relationship:

1/(1-x) = 1 + x + x**2 + x**3 + x**4 ... (continued; x < 1)

An alternative is

1/(1-x) = (1+x)*(1+x**2)*(1+x**4)...
 
K

Keith Thompson

Krypto said:
The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7

A person was mistaken. The lowest non-negative value for which it
fails is 7. The highest non-negative value for which it succeeds is
384. (I didn't try it for negative values.) But the pattern of
failures (difference between the result of the expression and N/7) is
interesting, and may suggest that a correct answer would look similar
to what you wrote.

Here's my test program. WARNING: It will produce huge amounts of
output. Run it as "./prog | more", or "./prog | head -100", or
equivalent.

#include <stdio.h>
#include <limits.h>

#define DIV_BY_7(N) (((N)>>3) + (((N)-7*((N)>>3))>>3))

int main(void)
{
int i = 0;
while (1) {
int x = i / 7;
int y = DIV_BY_7(i);
printf("%6d ", i);
if (x != y) {
printf("%6d", x - y);
}
putchar('\n');
if (i == INT_MAX) {
break;
}
i++;
}
return 0;
}
 
K

Keith Thompson

We were assuming that unsigned ints are 32 bits, which is of course not
guaranteed, but arithmetic on unsigned ints *is* guaranteed to work
modulo 2^N, where N is the number of bits. For signed integers,
anything may happen.

To be painfully precise, N is the number of value bits. Unsigned
types are allowed to have padding bits as well, which do not
contribute to the value.

Results are reduced modulo (MAX+1), where MAX is the maximum value of
the unsigned type, also expressible as (type)-1.
 
R

Richard Harter

How will it work ?

/* ans = x/7, accuracy up to 51 bits module corner cases, code untested
and will probably fail within 3 bits of maximum int. The idea is to
exploit the formula 1/(1-x) = (1+x)*(1+x^2)*(1+x^4)...
*/

ans = x + x>>3;
ans += ans * (x>>6);
ans += ans * (x>>12);
ans += ans * (x>>24);
ans = ans >>3;
 
F

Flash Gordon

Krypto wrote, On 01/02/07 20:27:

Subject: division by 7 without using division operator
The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7

If we put in N=7 we get:
(7>>3) + ((7 - 7*(7>>3)) >> 3)
=> 0 + ((7 - 7*0) >> 3)
=> (7-0) >> 3
=> 7 >> 3
=> 0

I think you should not trust what that person tells you. Either that or
take a lot more care in listening and noting down what they tell you.

Or to put it in C:

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

int main(int argc,char **argv)
{
unsigned long n;
char *end;

if (argc < 2) {
fputs("Give me a number!\n", stderr);
return EXIT_FAILURE;
}

n = strtoul(argv[1], &end, 10);

if (end==argv[1] || *end) {
fputs("Give me a number!\n", stderr);
return EXIT_FAILURE;
}

printf("%lu / 7 = %lu\n", n, (n>>3) + ((n-7*(n>>3))>>3));

return EXIT_SUCCESS;
}

markg@brenda:~$ gcc t.c -ansi -pedantic -Wall -W -O3
markg@brenda:~$ ./a.out 7
7 / 7 = 0
markg@brenda:~$
 
C

CBFalconer

Richard said:
Ben Pfaff said:
.... snip ...


Actually, had you bothered to analyse it, you would have found that
it's about the only part of the program that is actually correct. :)

It also has a bug. If strlen(p) == 0, then q is pointing outside
any object, and the comparison q < r is illegal. Assuming the
initialization of q could be done, which is also not guaranteed.
 
D

Dik T. Winter

> The correct answer as told to me by a person is
>
> (N>>3) + ((N-7*(N>>3))>>3)
>
> The above term always gives division by 7

Except when N is a multiple of 7 and a large number of other cases.
Try it with N == 7.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top