maybe this actually belongs somewhere in this forum :D , but i'm more seasoned to the heap nowadays :D ... and since homer asked for some post, i'll relate something i've learned while programming in java (!) and post some rantings...

i was making a small demo with a ball bouncing in a little space with something i had called "physics" :D , in fact a simulated fluid slowdown that was achieved by multiplying the speed vector of the ball by for example 9/10 at etach timeframe. i was coding in j2ME for mobilephones (i'm telling my life here :) ) and there was no FPU guaranteed and i was doing everything fixed point by assigning bit lengs to things, and i loved it. on a side note ints are 32b on the jvm but if you design a fixed point program you cant use all 32 because when you'll multiply by something (in order to then divide by 65536 for ex)  the result has to fit in 32b... not like x86 where you can have EDX:EAX. (or maybe theres something i dont know bout fixed point) .

to be fair, there are LONG ints in the jvm (64b), but i wasnt willing to use them because i supposed (maybe wrongly) that the damn mobilephone was 32b and that anything else would be emulated by the JVM. on another side note, i find it very good that the bit size of number is well defined in java, not like some other language definition i wont name :)

well. now i'm there, bouncing my ball in some directions, and it slows down gracefully. no, wait, in the other direction it begins to slow down, then it steadily slides at a constant speed towards minus infinity.

so. it took me some time to work this one out. in fact i was soing the "mul by 9/10 each timeframe" thing by doing MUL 9*65536/10, SHR 16, or something. problem is, SHR is not exacly like DIV. the damn negative numbers are rounded towards minus infinity. and so, if the number is positive, with many iterations of (*9/10) it becomes zero. if the number is negative it never gets "smaller" (abssolute value) than something like -10 (i think, didnt really investigate). and my ball never gets still!  whose fault?

the fault of the clever guys who decided that 2-complement was a good, natural, simple, and elegant way of representing negative numbers. and this leads us back to a thread i posted ages (..) ago ! :) argh! i told you it was bad! :)

okay, so with my system (sign bit + absolute value) it would take some special hardware to work. so what? its not that complicated! (someday i'll take a piece of paper and write the logic that performs this :) ). now we make weird things to get the absolute value of a number, we must take the absolute value in hardware to do a multiplication... i'm sure there are more.  but now lazy people use the fpu for doing everything, relying on the precision to hide their lack of mastering the precision errors... but they only postpone the judgment day :) , cause fpu, be it 32, 64, 80 or 2^128 bits, also generates roundup errors! haha! :) and even the hardware guys, the pure amongst the pure, are selling their souls :) to the devil by spending every bit of their energy to develop FP units that will seem to perform as fast as integer logic! so then software morons can come laughing and say "you see, its no use doing integer, nowadays FPU is faster, plus you're a moron etc" :) but the truth is, with the same technology its obvious that an ALU can always be faster than an FPU, cause for an FP op there are several AL ops involved. dont you see that, sinners ? :) then the problem of it being faster _today_ is only a matter of CPU design politics. if FADD is 1 clock and ADD 1 clock, well it doesnt mean that if you were running 10 times faster you'd not see the difference. (hmm of course to know wether my fixed point "software emulation" of high-range number operations would be better than a hardware FPU is another question :) . i'm just saying ppl take the FPU for granted as being not penalizing and that teh bad thing).

hmm, where was i again? :) , yeah, thats pretty much all for now. good night, kids! i've witnessed so many bugs in my first internship (school s over now! i'm grown up!) working on mobilephones (well actually no wonder cause the company was just porting games and my job was debug) that i cant be surprised by anything now. some bug froze the device to the point you had to remove the battery.

comment! people! otherwise i'll have been typing this crap for nothing! :)


Posted on 2006-11-23 21:22:02 by HeLLoWorld
Your method of slowing down 'velocity' would require a simple test of the high bit (negative flag bit) to check for 'underflow' , and clamp the velocity to zero at that point.
The main thing to remember when programming physics simulations is that we're not attempting to EMULATE reality, we're SIMULATING it.. therefore such cheap tricks are perfectly valid !
Nice to see someone else is interested in this topic :)
Posted on 2006-11-24 00:18:10 by Homer
Some bug froze the device to the point you had to remove the battery.

Lucky you, when my Palm devices froze to such an extent, I had to wait for the damn battery to drain all day :)

As for 16:16 mul in Java:

public static int mul(int a,int b){
int c,d;
boolean neg=false;
if(a<0){a=-a;neg=true;}
if(b<0){b=-b;neg=!neg;}
c=a&65535;
d=b&65535;
a=a>>16;
b=b>>16;
if(neg){
// is negative
return -(a*b+((a*d+c*b)>>16));
}
return a*b+((a*d+c*b)>>16);

}

System.out.println(mul(65536*(-10)/4,(65536*9))); // prints -22 ^_^

When I look at the code... ouch there went the speedup ^^". So, using "long" could be better (in the BlackBerry docs, it's stated it's 2-4 times slower than int). Still, I have no java-enabled phone to benchmark..

So, see the 2-complement code is not at fault, since the one's complement Java code to do this would be as fast :). Like I had said in my response to your previous post about 2-complement, you shouldn't spend time on getting angry at things that you can never change - instead, you should invest time and effort to beat the problems in the given environment/tools. Like you, I kinda hate it that not even one cpu has instructions to handle 565 bitmap-data... Even though for 10years PCs needed it, and now mobile devices need it a lot.

But that's all problems of mobile devices now (sucks to be a mobiledev developer like us :) ).

I envy you about the school... my uni is taking way too much time and money, and thus I'm at zero with both >_< . It's kinda my reason to not post any new topics here now, save for just short'n'quick solutions to problems users have.
Posted on 2006-11-24 00:31:15 by Ultrano
HeLLoWorld

...SHR is not exacly like DIV. the damn negative numbers are rounded towards minus infinity. ...


    Yes, that cannot be helped.  By the way, you MUST use SAR for negative numbers instead of SHR, or you will convert it to a positive number right away, which is obviously wrong.  If you want to round a negative number toward zero, negatate it first (NEG), then SHR, and finally NEG again.  Ratch
Posted on 2006-11-24 14:32:43 by Ratch
Why won't you simply multiply by 10 and then divide by 9 using those funny magic numbers?

// division of a 32-bit 'number' by 9
int number = 7, result;
long tmp = number;

result = ( ( 3817748708 * tmp) >>> 35 );

or something like that, I'm too sleepy atm. it's probably possible to avoid using longs.
Posted on 2006-11-24 19:15:50 by ti_mo_n
homer:
i think you misunderstand. problem was not the number is becoming negative too fast and going under zero. problem is negative numbers never reach zero.

ultrano:
Lucky you, when my Palm devices froze to such an extent, I had to wait for the damn battery to drain all day

ouch! :)
i dont fully understand your code since it strips one bit so is it one-complement...
goog luck with studies.

ratch:
YES, sar is needed. i didnt think of test/neg/sar/neg to avoid div.
funny thing is, in JAVA, >> operator does sar and >>> does SHR. at first i thought it was a mistake in the docs.(or ?)

ti_mo_n:
i dont really understand how those magic numbers work... however its still a MUL, so its still better to use shifts if possible. but now you make me think...maybe with some similar way i can multiply by 9/10 with one single MUL...


Posted on 2006-11-26 06:51:08 by HeLLoWorld
Well, magic numbers are used when you want to divide using multiplication. Teh above example divides (assuming that I didn't make any mistakes :P ) 'number' by 9 and stores the result in 'result'. Try it and see for yourself. The idea behind this has been explained thoroughly on this forum. Try searching for 'magic numbers'. Additionally, not so long ago, SpooK put somewhere here a link to one of the MSDN blogs where this method has been explained.

As for the JAVA:
>>   -  SAR (arithmetic shift right)
>>> -  SHR (logical shift right)


/edit:
The code from my previous post works. I've tested it.

Example:
Let's try to divide 81 by 9.
we calculate ( ( 81 * 3817748708 ) >>> 35 )
64 bit: (81 * 3817748708) = 309237645348
(309237645348 >>> 35 ) = 9,0000000010477378964424133300781
And this is, of course, 9 because the result gets truntacted into a 32-bit integer.
Posted on 2006-11-26 09:14:22 by ti_mo_n