 Programming Challenges - Page 2

# Thread: Programming Challenges

1. Checking up the definition of (a+ib)(c+id), it's
(ac-bd) + i (ad+bc)

which is what bwkaz found.

However, the question was:
Compute the complex product ( a + ib ) * ( c + id ) using only three real multiplications

We've only used 1 multiplication, and that's multiplying (ad+bc) by i.
The only further step I could find was:

i((1/i)(ac-bd) + (ad+bc))

but nothing else. Any other takers?

After I was so pleased with my web server 2. Strogian, you can effectively use division, because if you want to divide n by 7, just multiply it by 1/7.

3. Registered User
Join Date
Jul 2003
Posts
28
Originally posted by o0zi
Checking up the definition of (a+ib)(c+id), it's
(ac-bd) + i (ad+bc)

[snip]

We've only used 1 multiplication, and that's multiplying (ad+bc) by i.
The only further step I could find was:

No, it's not a trick like that. It would still take 4 real multiplications to compute (ac-bd) and (ad+bc). There is a way to do it so you really only have to compute 3 products; and though it takes 1 extra addition and 2 extra subtractions, you would still get savings from not having to do the more expensive multiplication.

Here's another challenge. You can waste alot of multiplications evaluating a polynomial such as a x^3+b x^2+ c x + d , but its possible to evaluate an n degree polynomial with only n multiplications. Can you figure it out? Don't forget that computing x^3 takes 3 multiplications in itself.
Last edited by grady; 08-21-2003 at 09:36 AM.

4. Registered User
Join Date
Jun 2000
Location
Houston, TX, USA
Posts
1,290
grady: computing x^3 only requires 2 multiplications last time I checked. However, getting it to n is tougher <edit> No, it's not, I just forgot how to do it. I'll hack together a solution now.</edit>
Last edited by Stuka; 08-21-2003 at 12:59 PM.

5. Registered User
Join Date
Mar 2001
Posts
729
I could do it if there weren't any coefficients, does that count? 6. Registered User
Join Date
Jul 2003
Posts
28
Originally posted by Stuka
grady: computing x^3 only requires 2 multiplications last time I checked.
The summer must be turning me into an imbicile. The n is correct. You can evaluate the polynomial with n products.

Here's another challenge: Write a function using only bit operations that can sum any two signed integers. No + or - is allowed anywhere in the function.

7. Registered User
Join Date
Apr 2001
Location
SF Bay Area, CA
Posts
14,947
Originally posted by grady
Here's another challenge. You can waste alot of multiplications evaluating a polynomial such as a x^3+b x^2+ c x + d , but its possible to evaluate an n degree polynomial with only n multiplications. Can you figure it out? Don't forget that computing x^3 takes 3 multiplications in itself.
Sure, just factor it.

Oh, wait... not all polynomials factor... Here's another challenge: Write a function using only bit operations that can sum any two signed integers. No + or - is allowed anywhere in the function.
Code:
```int sum(int num1, int num2)
{
int result = 0;
int i, carry = 0;

for(i=0; i<31; i++) {   /* these +'s don't count, do they? */
result |= (num1 ^ num2) & (1<<i) | carry;
carry = ((num1 & num2) & (1<<i)) << 1;
}

if(carry) {
fprintf(stderr, "Overflow.\n");
}

return result;
}```
I think. Haven't tested it, but from what I remember from Computer Architecture, the non-carry bits are just XOR, and carry is determined by ANDing and then shifting left one. Signed vs. unsigned matters not one bit, because signed integers are two's complement, they're equivalent.

8. Really bored person
Join Date
May 2003
Posts
145
This function is limited, but for all practical purposes, it works.

Code:
```#include <iostream>

using std::cout;

int add(int a, int b) {
int c=0, carry=0;
for (int i=1;i<9999999;i*=2) {
int bit1 = a&i, bit2 = b&i;

if ((!(bit1|bit2)) && carry) {
carry--;
bit1 = 1;
}

if (bit1&bit2) {
bit1 = bit2 = 0;
carry++;
}

if(bit1^bit2)
c |= i;
}
return c;
}```

9. ## Programming challenge

Write a short program that asks for your height in integer inches and then convert your height to feet and inches. Have the program use the underscore character to indicate where to type the response. Also, use a const symbolic constant to represent the conversion factor.

10. Registered User
Join Date
Jul 2003
Posts
28
bwkaz said

Sure, just factor it.

Oh, wait... not all polynomials factor...
They might not factor but you could do it this way by calculating all of the roots to the desired precision, however this isn't the best way to solve the problem

http://mathworld.wolfram.com/Fundame...ofAlgebra.html

bwakz, cfaun5, no arithmetic is allowed anywhere in the function, pretend your writing a multiprecision library and you want it to execute as fast as possible.
Last edited by grady; 08-22-2003 at 12:50 AM.

11. Registered User
Join Date
Mar 2001
Posts
729
Ooh! Ooh! I got it! Well, here's what I got. From here, the program is probably simple. ax^2+bx+c -> x(ax+b) + c
ax^3+bx^2+cx+d -> x(x(ax+b) + c) + d
...and so on...

12. Registered User
Join Date
Mar 2001
Posts
729
And here's the addition one: (I assumed unsigned numbers, but negatives are designed to work seamlessly with an adder, right?)

Code:
```int fastadd(unsigned int a, unsigned int b)
{
int tmpa;

do {
tmpa = a ^ b;
b = (a & b) << 1;
a = tmpa;
} while (a && b);

return a|b;
}```
I think that's right.. It might actually be more efficient, though, if I just let it go through the one extra add cycle instead of checking both a and b each cycle.

13. Here's another challenge: generate some random numbers without using any in-built random functions (like rand).

14. Ok, I've got some good decyphering challenges made especially for you guys. These are not impossible like some of the previous posts. They will all decypher into english text. Please Post Your Answer As An Attachment. Have fun guys. Level - Easy:
J}hjqqjsy1~tzgwtpjymjhtij3Wfsp2st{nhjM9}tw

Level - Medium
144 192 208 58 202 178 164 202 48 200 194 198 172 202 202 212 176 192 192 170 36 116 48 188 180 188 194 198 172 200 200 172 170 60 180 190 202 172 198 188 172 170 180 164 202 172 168 198 164 168 184 172 198

Level - Hard
GTSP0@RRTPTRVTNBPYVNY3=>

Please Post Your Answer As An Attachment.

15. Bad Speller ^^
Join Date
May 2001
Location
Uh, I'm somewhere where I don't know where I am.
Posts
1,228
Originally posted by bwkaz
Sure, just factor it.

for(i=0; i<31; i++) { /* these +'s don't count, do they? */
Easy way out:

unsigned int i;

for (i = 4294967295; i; i >>= 1)

You'll get 32 shifts until i = 0, or 31 until i = 1, there's your counter.
Last edited by tecknophreak; 08-22-2003 at 09:25 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•