 # Programming Challenges

• 08-21-2003, 03:29 AM
o0zi
Checking up the definition of (a+ib)(c+id), it's

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:

but nothing else. Any other takers?

After I was so pleased with my web server:(
• 08-21-2003, 03:31 AM
o0zi
Strogian, you can effectively use division, because if you want to divide n by 7, just multiply it by 1/7.
• 08-21-2003, 09:30 AM
Quote:

Originally posted by o0zi
Checking up the definition of (a+ib)(c+id), it's

[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.
• 08-21-2003, 12:56 PM
Stuka
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>
• 08-21-2003, 02:34 PM
Strogian
I could do it if there weren't any coefficients, does that count? :p
• 08-21-2003, 03:21 PM
Quote:

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.
• 08-21-2003, 07:10 PM
bwkaz
Quote:

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... :p

Quote:

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.
• 08-21-2003, 07:27 PM
cfaun5
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; }```
• 08-21-2003, 07:42 PM
kshim5
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.
• 08-22-2003, 12:39 AM
Quote:

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.
• 08-22-2003, 01:32 AM
Strogian
Ooh! Ooh! I got it! :D

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...
• 08-22-2003, 02:00 AM
Strogian
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.
• 08-22-2003, 03:39 AM
o0zi
Here's another challenge: generate some random numbers without using any in-built random functions (like rand).
• 08-22-2003, 03:45 AM
Sepero
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=>

• 08-22-2003, 08:11 AM
tecknophreak
Quote:

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.