oldk1331 wrote:
>
> Common Lisp standard provides ISQRT, which satisfies
> the documentation of approxSqrt, well, approxSqrt requires:
> -1 < approxSqrt(n) - sqrt(n) < 1
> but ISQRT is more accurate:
> -1 < ISQRT(n)$Lisp - sqrt(n) <= 0
>
> Further more, ISQRT is faster, at least in SBCL:
>
> (35) -> [approxSqrt(x) for x in 10^21+(1..2*10^5)];
>
> Type: List(Integer)
> Time: 0.77 (EV) = 0.77 sec
> (36) -> [ISQRT(x)$Lisp for x in 10^21+(1..2*10^5)];
>
> Type: List(SExpression)
> Time: 0.41 (EV) = 0.41 sec
>
> Our definition for approxSqrt is unusual, compare with
> Wikipedia: https://en.wikipedia.org/wiki/Integer_square_root
Our definition is computable with reasonable efficiency using high
level operations. For moderate arguments final adjustment to
satisfy requirements of ISQRT may add nontrivial cost. ISQRT
may take advantage of low level representation of numbers, so
may be faster due to this. OTOH in the past there were Lisp
implementation with very slow ISQRT.
> And as I said before, this is a big source of inaccuracy in
> sqrt$Float.
Concerning inaccuracy of floating point functions I have
mixed feeling. On one hand it would be nice to get
accuracy with say less than 1 bit error. But the only
way to get this is to perform all intermediate calculations
at increased accuracy. Which in turn means that essentially
all high level formulas would be wrong. Namely before
applying formula we would have to increase accuracy, which
means that we could not use generic implementation via
high level formula. Currenly many elementary functions
have special implementation. But for example 'acsc',
'asec' and 'nthRoot' are generic. Also _integer_ power have generic
implementation via repeated multiplication. Consequently,
some functions are subject to error accumulation.
I must admit that IMO currently we do not have manpower
necessary to guarantee error bounds for floating point
functions. More precisely, with current implementation
error bounds depend on error analysis and this is
extremaly laborious. Rather, I think that we should
look at Interval. Interval is supposed to give
correct error bounds and we should make sure that
it works. Also, it would be good to have (center, bound)
representation for real and complex intervals. Such
representation should be much faster at large
accuracies and complex version should behave better
than Complex(Interval). In principle on top of
interval arithemtic we could provide floating
point functions with strict error bound. Efficiency
would be lower than direct implementation, but
functions would be nuch easier to implement. In
particular, we could eliminate anayslis of rounding
errors.
> So I want changes to approxSqrt, opinions?
I think that the rest of code should work correctly with
current definition of 'approxSqrt'. I mean: if there is
problem code calling 'approxSqrt' should be fixed.
Due to higher speed of sbcl 'ISQRT' we may prefer to
use it in heavier computations. OTOH if we just
replace 'approxSqrt' by 'ISQRT' it will be harder to
test if code still works with specification of
'approxSqrt'. It seems that 'approxSqrt' has
only limited number of uses, so either way it
seem to be no big deal.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
