| |
Luke
Registered: Dec 2004
Posts: 19 |
8 or 16bit muls/divs
About multiply:
Bad one:
a*b=((a+b)/2)^2-(((a+b)/2-b))^2 with x*x matrix
It's near 30-40 cycles, but unstable with (a+b)bit0 bcoz ror after adc.
Some ppl using "nybble tables" $0n x $xy with $1000 size of tables and swap+add, but more than 50 cycles left.
And last bad is old asl bcc adc ror routine, but very slow
like 80+ cycles.
Now I trying to do any 16x16bit signed multiply, but it's really hard to make "short time" routine. Anyone got any idea?
About Divu/Divs
Classical lsr bcs sbc rol too slow.
But a/b= e^(lna-lnb) looks quite fast with e^x matrix, but
quite inaccurate.
Somebody got other "faster" idea for it? Particular 16/16bit routines.
|
|
... 29 posts hidden. Click here to view all posts....
|
| |
ready.
Registered: Feb 2003
Posts: 441 |
@WVL: I only saw your post now, you must have edited it after I read it the first time. Your method seems very interesting and for zooming it might be the fastest, if not using Oswald's tables.
Anyhow, just today I improved my routine greatly. I noticed that if I have 256 volume/zoom levels instead of 16, 32, 64,.. I can cut the code greately:
K*L/256=M
K: sampled data
L: volume/zoom level
M: scaled sample
lda K
ldy L
jsr mult ;K*L = (byte low, byte high) = (x reg, accu)
sta M
thus getting rid of all the ror lsr and having 256 levels of resolution! After all in the application I am working on 256 levels are better than 16.
Furthermore the X register, which is the least significant part of the multiplication, contains the reminder, which might come handy in some applications. In fact:
K*L=256*M+X
Still I think WVL's method is faster. I will give it a try sooner or later. Great idea! |
| |
Skate
Registered: Jul 2003
Posts: 494 |
@ready: please read Oswald's and my 5 years old posts above and compare with what you've come up with today. :) |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
WVL's post is interesting looks exactly like the square method, but using cos/sin? WTF?! I dont get it. :) |
| |
ready.
Registered: Feb 2003
Posts: 441 |
@skate: ah, I shuold have gone through this old thread before posting!! Well, I kinda thought that this way must have been already used somewhere.
Anyhow, it's always nice to make it by yourself without looking at the solution, even if somebody has already made it before :)
|
| |
WVL
Registered: Mar 2002
Posts: 902 |
Quote: WVL's post is interesting looks exactly like the square method, but using cos/sin? WTF?! I dont get it. :)
Ha! Finally I managed to outsmart Oswald!
I have to say that i only once used this technique before, in that particular case to let 2 movements warp into eachother. It was the part in Arcanum with the vertical bars. The nice thing was that all the movements are made from sines ;) So I already had my x1 for movement 1 and x2 for movement 2. Then i just multiplied the value for movement 1 from 1...0 (changing in time) and for movement 2 from 0...1 (changing in time) and the result is a smooth change in the different movements without any effort :)
Anyway, think of it like this :
if value i want (A) is 255 and x is such that cos(x)=255 (x=0') and my y = 0' (multiplication of 1), you get :
C = (cos(x-0) + cos(x+0))/2 = (255 + 255)/2 = 255 (I multiplied by 1).
now, if you select y such that the values are opposite in phase (ie y = 90 degrees), you get that both cos values added give 0.
change the value of y inbetween 0' and 90' and the result is a smooth variance from 0...255 (or any value you like as a result). The only thing you have to do is select the appropiate y-value from an inverse cosine table.
Note that this way of multiplying is not good at all if you first need to get the value of x (but for samples, we simply store x instead of A!)
Oh, one more thing :
the nice thing about this is that it automagically also works OK with negative numbers, unlike the squares method where you have to take care of some stuff by yourself. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
You got me so many times already :) its also interesting from the math viewpont, how come two so different things are so similar ? tho there's an extra 'lookup' on the left side of the equation. apart from that its the same code. BTW signs also automagically work in the squares method, but it only works for +/-64, and I guess the same is true for sines, because everything is the same except the table data :) |
| |
WVL
Registered: Mar 2002
Posts: 902 |
Well, maybe it's easier to understand it if you relate it to
e^a * e^b = e^(a+b)
knowing that you can write sines as the imaginary part of e^ix and cosines as the real part of e^ix... They are heavily related :) |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
WVL:
I had a vague memory of my old algebra textbook mentioning that trigonometric identities and tables had once been used to carry out multiplication and division, before the discovery of the logarithm. I just looked it up and apparently the method is called prosthaphaeresis (which sounds more like a disease than an algorithm if you ask me.)
I guess that just goes to show that there's nothing new under the sun. I suppose the ancient Babylonians used the table-of-squares method to do all of their 8-bit arithmetic... |
| |
ready.
Registered: Feb 2003
Posts: 441 |
ah, ah, back in school my math teacher always insisted on these prosthaphaeresis formulas and I have always wondered for what I would ever use them in real life. Well, didn't know I was going to make demos about 20 years later :)
|
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Quote: Well, maybe it's easier to understand it if you relate it to
e^a * e^b = e^(a+b)
knowing that you can write sines as the imaginary part of e^ix and cosines as the real part of e^ix... They are heavily related :)
Yes but this has nothing to do that you can use it for a multiplication. You can use almost any concave function which starts at 0 and a lookup table to make a multiplication.
|
| Previous - 1 | 2 | 3 | 4 - Next |
