File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Multiply no star. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Multiply no star." Watch "Multiply no star." New topic
Author

Multiply no star.

Saifuddin Merchant
Ranch Hand

Joined: Feb 08, 2009
Posts: 605

Hardly any action here just trying to create a stir

Write a program to multiple two floating point numbers.
Twist: Do not use the “*” (multiplication sign) in the entire program.

Ok I admit I just picked it up from my blog - maybe its too easy for you folks, is it? ;)

Cheers - Sam.
Twisters - The new age Java Quiz || My Blog
Brian Legg
Ranch Hand

Joined: Nov 07, 2008
Posts: 488
This would be really easy if it were 2 integers... but floats? I imagine it would have something to do with bit shifting which I am terrible at. I think I could do it by using the opposite of the * sign, the / sign. Multiplying is just dividing by 1 over your divisor... but to do this without using the division sign either I think you could keep checking the floats to see if they are whole numbers, if not then shift the decimal to the right. Continue in this pattern until you have 2 whole numbers. Add them together in a loop until you have cycled the correct number of times, then shift the decimal back to the left however many places you had to move it to the right to get both floats to be whole numbers.

I hope that made sense.... let me know if I am on the right track or if I'm way off.

Interesting problem.


SCJA
~Currently preparing for SCJP6
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41524
    
  53
What other functions are allowed? It's easy with logarithms and exponentials:

a * b = exp(log(a) + log(b))


Ping & DNS - my free Android networking tools app
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11230
    
  16

i don't see what difference it makes as to being a float or an int... the process is the same. Multiplication is really just addition. 25 times 32 can be though of as adding 25 to itself 35 times.

123.455 times 78.389 is the same as adding 123455 to itself 78389 times, then fine-tuning the decimal point. Use some String methods to determine how many total digits are to the right of the decimal in each of the multiplier/multiplicand, then again using String methods insert a decimal back into the sum.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Brian Legg
Ranch Hand

Joined: Nov 07, 2008
Posts: 488
That's basically what I was getting at Fred with my long explaination

I'd like to know if Ulf's suggestion works, I am not to savy on logs
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11230
    
  16

Brian Legg wrote:That's basically what I was getting at Fred with my long explaination

I'd like to know if Ulf's suggestion works, I am not to savy on logs


I can tell by that you're pretty young. Slide rules, what folks used before there were such things as hand calculators, worked by adding logarithms. That used to be the ONLY way to do multiplication (well, there was always pencil and paper).

so yes, Ulf's suggestion is 100% valid.
Brian Legg
Ranch Hand

Joined: Nov 07, 2008
Posts: 488
That takes all the fun out of it

I was all ready to write up an overcomplicated method to solve it. Would dividing by 1/divisor also work as well, right?

And your assessment of my age is correct, at least I like to think so
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
Brian Legg wrote:I was all ready to write up an overcomplicated method to solve it. Would dividing by 1/divisor also work as well, right?

Yup.

There's also


Brian Legg wrote:I was all ready to write up an overcomplicated method to solve it.

Well, you can try solving a harder version of the problem, like "Write a program to multiple two doubles, without using '*' or any calls to any class or method you didn't write yourself." I think that's impossible unless we allow calling Double.doubleToLongBits() or Double.doubleToRawLongBits(). But I may be overlooking something. Once you've got the raw bits though, you can use just bit shifts and addition. Multiply the two integer mantissas as you described earlier, add the exponents, and renormalize the mantissa.
Brian Legg
Ranch Hand

Joined: Nov 07, 2008
Posts: 488
Mike Simmons wrote:"Write a program to multiple two doubles, without using '*' or any calls to any class or method you didn't write yourself."


I may take you up on that offer, but I would need more clerification on "method you didn't write yourself". Does this include the toString method? How restrictive are we getting here?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
I meant without any existing methods or classes, including those in String. And I should have also outlawed '/' to prevent the other solution you noted. I think this may make the problem impossible, so then I made an exception for doubleToLongBits(). The idea is to force the programmer to implement floating-point multiplication using only addition and bit-shifting.

But as I think about it, there's still another solution, somewhat slower, that uses only addition, no bit shifting, and no doubleToLongBits(). Probably a number of other solutions. Eh, it feels too much like I'm adding constraints just to force a single solution on the programmer. Which lacks elegance, as problems go. Oh well.
Brian Legg
Ranch Hand

Joined: Nov 07, 2008
Posts: 488
Still sounds fun Mike, I'll have to think on it!
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3007
    
    9
Mike Simmons wrote:But as I think about it, there's still another solution, somewhat slower, that uses only addition, no bit shifting, and no doubleToLongBits().

Thought about it some more, and I believe I misspoke here. It's possible to do much of the solution under these conditions, but I think eventually you need either bit shifting or division in order to create a double representing the result. Or various other methods like Double.longBitsToDouble(), or string methods followed by Doubple.parseDouble(), etc. Many possibilities, but you need something more than addition.
Saifuddin Merchant
Ranch Hand

Joined: Feb 08, 2009
Posts: 605

The solution I had in mind was using the '/' sign.
Ulf solution --> a * b = exp(log(a) + log(b)) is also pretty neat.

Sure you could go ahead do repeated addition (after taking care of the decimals) so that's a third possible solution.

Oh next problem coming up in some time
Brian Legg
Ranch Hand

Joined: Nov 07, 2008
Posts: 488
I have another "problem" but I think it may be too easy. I'll post it later today
Gabriel Claramunt
Ranch Hand

Joined: May 26, 2007
Posts: 375
I'll bet the IEEE float format has a multiplication algorithm that just involves shifts and logic operations, but I'm too lazy to search for it


Gabriel
Software Surgeon
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Multiply no star.