Programming Challenges - Page 2


Page 2 of 19 FirstFirst 12345612 ... LastLast
Results 16 to 30 of 279

Thread: Programming Challenges

  1. #16
    Join Date
    Aug 2002
    Location
    Essex, UK
    Posts
    937
    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. #17
    Join Date
    Aug 2002
    Location
    Essex, UK
    Posts
    937
    Strogian, you can effectively use division, because if you want to divide n by 7, just multiply it by 1/7.

  3. #18
    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. #19
    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.
    "I'm not closed-minded, you're just wrong" - Bucky Katt

  5. #20
    Join Date
    Mar 2001
    Posts
    729
    I could do it if there weren't any coefficients, does that count?

  6. #21
    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. #22
    Join Date
    Apr 2001
    Location
    SF Bay Area, CA
    Posts
    14,936
    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. #23
    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. #24
    Join Date
    Mar 2003
    Posts
    287

    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.
    Live free or die ... LINUX

  10. #25
    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. #26
    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. #27
    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. #28
    Join Date
    Aug 2002
    Location
    Essex, UK
    Posts
    937
    Here's another challenge: generate some random numbers without using any in-built random functions (like rand).

  14. #29
    Join Date
    Mar 2003
    Location
    Tampa, FL USA
    Posts
    2,193
    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. #30
    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.
    if (i_forgot && this_is_about_code)
    language = c++;

Posting Permissions

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