| Author |
Message |
Ben Hetland
Guest
|
 Posted:
Thu Sep 22, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Keith Thompson wrote:
| Quote: | Some languages have direct support for such types. In others, you can
always simulate it by using integer arithmetic and keeping track of
the delta yourself.
|
Careful! You also have to modify your arithmetic (the formulas) unless
you restrict yourself to only doing addition and subtraction. Otherwise
you might end up with the wrong amount of dollars... or wrong squares.
E.g., we keep track of length measurements in meters at 1 cm "delta".
(delta = 0.01). We measure an area at 5.25m X 10.1m, so we represent it as
a = 525
b = 1010
Then we calculate using the very straightforward and obvious formula
area = a * b,
which is computed as 530250. Remembering the "delta", we might end up
concluding that the area is 5302.50 m2, which is not just a bit wrong...
We would need a different formula, except it has to be in integer too,
right? Otherwise there's no point in using "fixed point" arithment if we
often need to revert to floating points even for intermediate
calculations anyway.
That was a very simple formula; but think of a more real-world example
where a "correction factor" is no longer so obvious.
We might deduce some formulas though, but it would require us to rewrite
every operator in the original formula. Ignoring rounding errors and
overflows for now, perhaps using some function substitutes for each
operator, we could end up using integer arithmetic in the following way:
delta = 0.01
f = 1/delta -> f=100 (the f is integer!)
a * b -> (a * b) / f
a / b -> (a * f) / b
1 / a -> (f * f) / a
a ^ 2 -> a * a -> a * a / f
a ^ 3 -> (a^2)*a -> (a^2)*a/f -> (a*a/f)*a/f
a ^ n -> ((...
(( ((a(1) * a(2))/f) * a(3) )/f)
*...) * a(n))/f (n whole number)
a ^ b -> suggestions anyone?
Think how that translates just for a simple interest calculation like
fv = pv * (1 + r/100)^n
:-)
Does anyone know how that is implemented for languages that do support
this kind of data type when the underlying hardware does not support it
directly? I should think that if everything in this manner translates
into some "intrinsic routines" or similar support code, then easily the
expected gain (speed) from using integer instead of floating point
operations is lost to all the extra operations involved.
-+-Ben-+- |
|
| Back to top |
|
 |
Keith Thompson
Guest
|
| Posted:
Fri Sep 23, 2005 12:13 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Ben Hetland <ben.a.hetland@sintef.no> writes:
| Quote: | Keith Thompson wrote:
Some languages have direct support for such types. In others, you can
always simulate it by using integer arithmetic and keeping track of
the delta yourself.
Careful! You also have to modify your arithmetic (the formulas) unless
you restrict yourself to only doing addition and subtraction. Otherwise
you might end up with the wrong amount of dollars... or wrong squares.
|
Of course; that's part of what I meant by "keeping track of the delta
yourself" (though I suppose I should have been more explicit).
[snip]
| Quote: | delta = 0.01
f = 1/delta -> f=100 (the f is integer!)
a * b -> (a * b) / f
a / b -> (a * f) / b
1 / a -> (f * f) / a
a ^ 2 -> a * a -> a * a / f
a ^ 3 -> (a^2)*a -> (a^2)*a/f -> (a*a/f)*a/f
a ^ n -> ((...
(( ((a(1) * a(2))/f) * a(3) )/f)
*...) * a(n))/f (n whole number)
a ^ b -> suggestions anyone?
Think how that translates just for a simple interest calculation like
fv = pv * (1 + r/100)^n
:-)
|
Exponentiation (if the language supports it) is just repeated
multiplication.
| Quote: | Does anyone know how that is implemented for languages that do support
this kind of data type when the underlying hardware does not support it
directly? I should think that if everything in this manner translates
into some "intrinsic routines" or similar support code, then easily the
expected gain (speed) from using integer instead of floating point
operations is lost to all the extra operations involved.
|
Addition and subtraction are trivial. Multiplication just requires
multiplying the integer result by the delta. Division can be a bit
more tricky; you might need extra precision for an intermediate result
(I don't remember the details). There shouldn't be any need for any
intrinsic routines; most or all of it can be done with inline code.
And you'll get better performance if the delta is a power of two.
<OT>Ada has built-in user-defined fixed-point types.</OT>
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this. |
|
| Back to top |
|
|
Hank Oredson
Guest
|
| Posted:
Fri Sep 23, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Bruce Roberts" <ber@bounceitattcanada.xnet> wrote in message
news:_FfYe.8199$0u2.1520116@news20.bellglobal.com...
| Quote: |
"Hank Oredson" <horedson@earthlink.net> wrote in message
news:qd6Ye.1118$zQ3.58@newsread1.news.pas.earthlink.net...
trim of an excessively long, non-contributory quote
Read Knuth.
Skybuck has trouble reading the help. Knuth is, perhaps, asking too much.
You have not yet defined the problem you wish to solve.
See if you can do that.
Bet you can't.
A sure bet if I ever saw one.
|
Yes, suspect that is true. What do I win?
Kinda fun watching folks post all kinds of "solutions"
to a problem which is not yet defined, while ignoring
all the important issues.
--
... Hank
http://home.earthlink.net/~horedson
http://home.earthlink.net/~w0rli |
|
| Back to top |
|
|
Ben Hetland
Guest
|
| Posted:
Fri Sep 23, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Keith Thompson wrote:
| Quote: | Exponentiation (if the language supports it) is just repeated
multiplication.
|
This is true only for integer exponents!
(As I illustrated with my "a^n" example.)
When the exponent also has a fractional part (as in "a^b"), then it is
not more so trivial. I assume this is true even if the "fractional
exponent" is a "fixed format represented as integer".
-+-Ben-+- |
|
| Back to top |
|
|
John Woodgate
Guest
|
| Posted:
Fri Sep 23, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
I read in sci.electronics.design that Ben Hetland
<ben.a.hetland@sintef.no> wrote (in <dh0p89$e6j$1@orkan.itea.ntnu.no>)
about 'Point on Line Segment in 2D. Which code is faster ? Can you
improve it ?', on Fri, 23 Sep 2005:
| Quote: | Keith Thompson wrote:
Exponentiation (if the language supports it) is just repeated
multiplication.
This is true only for integer exponents!
(As I illustrated with my "a^n" example.)
When the exponent also has a fractional part (as in "a^b"), then it is
not more so trivial. I assume this is true even if the "fractional
exponent" is a "fixed format represented as integer".
|
For rational exponents, the operation involves multiplication and
division, or at least one single division to evaluate a reciprocal.
Irrational and transcendental exponentiation is witchcraft and should be
proscribed. (;-)
--
Regards, John Woodgate, OOO - Own Opinions Only.
If everything has been designed, a god designed evolution by natural selection.
http://www.jmwa.demon.co.uk Also see http://www.isce.org.uk |
|
| Back to top |
|
|
Dik T. Winter
Guest
|
| Posted:
Fri Sep 23, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
In article <lpNDNRWn5+MDFwQl@jmwa.demon.co.uk> John Woodgate <noone@yuk.yuk> writes:
....
| Quote: | When the exponent also has a fractional part (as in "a^b"), then it is
not more so trivial. I assume this is true even if the "fractional
exponent" is a "fixed format represented as integer".
For rational exponents, the operation involves multiplication and
division, or at least one single division to evaluate a reciprocal.
|
Only for integer exponents, for rational non-integral exponents you
need also roots. E.g. a^(1/2) = sqrt(a).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ |
|
| Back to top |
|
|
John Woodgate
Guest
|
| Posted:
Fri Sep 23, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
I read in sci.electronics.design that Dik T. Winter <Dik.Winter@cwi.nl>
wrote (in <In9tqA.9C4@cwi.nl>) about 'Point on Line Segment in 2D. Which
code is faster ? Can you improve it ?', on Fri, 23 Sep 2005:
| Quote: | In article <lpNDNRWn5+MDFwQl@jmwa.demon.co.uk> John Woodgate
noone@yuk.yuk> writes:
...
When the exponent also has a fractional part (as in "a^b"), then it is
not more so trivial. I assume this is true even if the "fractional
exponent" is a "fixed format represented as integer".
For rational exponents, the operation involves multiplication and
division, or at least one single division to evaluate a reciprocal.
Only for integer exponents, for rational non-integral exponents you
need also roots. E.g. a^(1/2) = sqrt(a).
|
They can be calculated to any desired degree of precision by
multiplication. Look up 'co-factors', which is how we used to find
square roots on a mechanical calculator.
--
Regards, John Woodgate, OOO - Own Opinions Only.
If everything has been designed, a god designed evolution by natural selection.
http://www.jmwa.demon.co.uk Also see http://www.isce.org.uk |
|
| Back to top |
|
|
Dik T. Winter
Guest
|
| Posted:
Sat Sep 24, 2005 6:28 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
In article <+E4VWoa2sANDFwYV@jmwa.demon.co.uk> John Woodgate <noone@yuk.yuk> writes:
| Quote: | I read in sci.electronics.design that Dik T. Winter <Dik.Winter@cwi.nl
wrote (in <In9tqA.9C4@cwi.nl>) about 'Point on Line Segment in 2D. Which
code is faster ? Can you improve it ?', on Fri, 23 Sep 2005:
....
For rational exponents, the operation involves multiplication and
division, or at least one single division to evaluate a reciprocal.
Only for integer exponents, for rational non-integral exponents you
need also roots. E.g. a^(1/2) = sqrt(a).
They can be calculated to any desired degree of precision by
multiplication. Look up 'co-factors', which is how we used to find
square roots on a mechanical calculator.
|
I know how to calculate square roots etc. Thank you very much. But
with your characterisation you can calculate *all* numbers of the form
a^b by only the operations multiplication and division, addition and
subtraction.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ |
|
| Back to top |
|
|
Keith Thompson
Guest
|
| Posted:
Sat Sep 24, 2005 7:26 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Ben Hetland <ben.a.hetland@sintef.no> writes:
| Quote: | Keith Thompson wrote:
Exponentiation (if the language supports it) is just repeated
multiplication.
This is true only for integer exponents!
(As I illustrated with my "a^n" example.)
When the exponent also has a fractional part (as in "a^b"), then it is
not more so trivial. I assume this is true even if the "fractional
exponent" is a "fixed format represented as integer".
|
That's true -- but if you're dealing with exponentation with a
non-integer exponent, you probably want to use floating-point anyway.
If you really need to compute a=b**c, where a, b, and c are all
fixed-point, you're likely to be better off converting b and c to
floating-point and then converting the result back to fixed-point.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this. |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in