Declaring return type of a function

[Jack]

I have a function that returns a list of integers and I want to apply the * operator to that list. Once the list gets beyond a certain size, I get a floating point error. How do I tell CCL that it's okay to use bignums for this calculation?

Thanks.

[Tim Bradshaw]

You don't need to. I suspect that the list is not actually a list of
integers but contains one or more floats, which is causing contagion &
then an overflow.

Something like this will ensure that floats in the list get rounded

(reduce (lambda (&optional (a 1) (b 1))
(* (round a) (round b)))
<list>)

[Espen Vestre]

Hi Jack!

Are you sure you get a "floating point error"? From your description, it
sounds like you apply * to a list that is longer than the maximal number
of arguments to * that CCL can take.

The standard solution to this (i.e. whenever you have a list of numbers
that may be arbitrary long and want to apply * or other similar
functions to it) is to use REDUCE instead of APPLY:

CL-USER 6 > (* 2 3 4 5 6 7)
5040

CL-USER 7 > (apply #'* '(2 3 4 5 6 7))
5040

CL-USER 8 > (reduce #'* '(2 3 4 5 6 7))
5040

--
(espen)

[Jack]

I just double checked and the only thing I do do the values I put in the list is initialize them to zero and call incf. They're definitely integers (fixnums, even), although I don't declare them as such.

[Espen Vestre]

Jack <jack.m...@gmail.com> writes:

> I just double checked and the only thing I do do the values I put in
> the list is initialize them to zero and call incf. They're definitely
> integers (fixnums, even), although I don't declare them as such.

Exactly which error do you get?
--
(espen)

[Kaz Kylheku]

On 2012-03-15, Espen Vestre <es...@vestre.net> wrote:
> Jack <jack.m...@gmail.com> writes:
>
>> I have a function that returns a list of integers and I want to apply
>> the * operator to that list. Once the list gets beyond a certain
>> size, I get a floating point error. How do I tell CCL that it's okay
>> to use bignums for this calculation?
>
> Hi Jack!

Careful! Words like that will now get you detained at airports in the US of A.

[rugilbert17]

On 15/03/2012 4:44 PM, Espen Vestre wrote:
> Jack<jack.m...@gmail.com> writes:
>
>> I have a function that returns a list of integers and I want to apply
>> the * operator to that list. Once the list gets beyond a certain
>> size, I get a floating point error. How do I tell CCL that it's okay
>> to use bignums for this calculation?
>
> Hi Jack!
>
> Are you sure you get a "floating point error"? From your description, it
> sounds like you apply * to a list that is longer than the maximal number
> of arguments to * that CCL can take.
>
> The standard solution to this (i.e. whenever you have a list of numbers
> that may be arbitrary long and want to apply * or other similar
> functions to it) is to use REDUCE instead of APPLY:

Clojure, of course, doesn't have this problem.

user=> (apply + (range 1000000))
499999500000

user=> (reduce + (range 1000000))
499999500000

[Jack]

On Thursday, March 15, 2012 1:44:41 PM UTC-7, Espen Vestre wrote:

Thanks for the idea. I switched to reduce and still got FLOATING-POINT-OVERFLOW detected with an error message that indicates that one of the numbers I pushed onto the list is being interpreted as 1.0 rather than 1.

Is it considered better form to use reduce rather than apply?

[Jack]

On Thursday, March 15, 2012 1:51:57 PM UTC-7, Espen Vestre wrote:

FLOATING-POINT-OVERFLOW detected
performing FLOAT on (1774816799345202714556665692160000000000
1.0)
[Condition of type FLOATING-POINT-OVERFLOW]

[Espen Vestre]

Jack <jack.m...@gmail.com> writes:

> Is it considered better form to use reduce rather than apply?

Yes, unless the number of arguments is quite limited (less than 50,
which is the lowest number that CALL-ARGUMENTS-LIMITS is allowed to have
according to the standard - on my 64 bit LW 6, it has the value 2047).
--
(espen)

[Espen Vestre]

Jack <jack.m...@gmail.com> writes:

> FLOATING-POINT-OVERFLOW detected
> performing FLOAT on (1774816799345202714556665692160000000000
> 1.0)
> [Condition of type FLOATING-POINT-OVERFLOW]

That large number looks like it might be the result of your apply, so
are you sure you're looking at the right place in your code? (I.e. are
you trying to do something with the result of the apply that may force
floating-point coercion?)
--
(espen)

[Jack]

On Thursday, March 15, 2012 1:29:31 PM UTC-7, Jack wrote:
> I have a function that returns a list of integers and I want to apply the * operator to that list. Once the list gets beyond a certain size, I get a floating point error. How do I tell CCL that it's okay to use bignums for this calculation?
>
> Thanks.

I found the problem. Oddly enough, it was me.

I left in a debugging statement with a ~F in it. That's where the floating point conversion blew up. Thanks for the assistance.

[Kaz Kylheku]

On 2012-03-15, Jack <jack.m...@gmail.com> wrote:
> Is it considered better form to use reduce rather than apply?

No. Using reduce when one could use apply is for pragmatic reasons (not
exeeding argument passing limits), not for reasons of form. Applying arguments
to a function is otherwise fine form.

The main job of reduce is to allow an arbitrary list of arguments to be
processed with a binary function. For instance, if the operator + was binary,
then reduce would still let you add three or more numbers in one operation.

(Applying a binary function to any number of arguments is ambiguous: do you want
left-associative, right-associative, or something else? reduce supports the
first two options.)

[Pascal J. Bourguignon]

Noot less than 50, less than CALL-ARGUMENTS-LIMIT, which can be quite
high, eg in SBCL:

% clall -r call-arguments-limit
Armed Bear Common Lisp --> 50
Clozure Common Lisp --> 65536
CLISP --> 4096
CMU Common Lisp --> 536870911
ECL --> 65536
SBCL --> 1152921504606846975

So if you suppose apply is faster than reduce, you could write:

(if (< (length list) call-arguments-limit)
(apply '+ list)
(reduce '+ list))

or even search on google groups for an older answer where I show how to
group the elements in the list by call-arguments-limit to use apply as
much as possible.


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Elias Mårtenson]

On Friday, 16 March 2012 05:21:08 UTC+8, Jack wrote:

> I found the problem. Oddly enough, it was me.
>
> I left in a debugging statement with a ~F in it. That's where the floating point conversion blew up. Thanks for the assistance.

That sounds very strange to me. Would you care to show the actual code?

I can't think of any situation where just printing the value as a float would be able to impact the value itself (unless there is a problem with CCL's type inference).

[Pascal J. Bourguignon]

Elias Mårtenson <lok...@gmail.com> writes:

> On Friday, 16 March 2012 05:21:08 UTC+8, Jack wrote:
>
>> I found the problem. Oddly enough, it was me.
>>
>> I left in a debugging statement with a ~F in it. That's where the floating point conversion blew up. Thanks for the assistance.
>
> That sounds very strange to me. Would you care to show the actual code?

(defun fact (x) (if (< x 1) 1 (* x (fact (1- x)))))
(format t "Result is : ~F~%" (fact 10))
(format t "Result is : ~F~%" (fact 100))
prints:
Result is : 3628800.0
Result is :
; Evaluation aborted on #<SYSTEM::SIMPLE-FLOATING-POINT-OVERFLOW
#x000334A53B78>.

> I can't think of any situation where just printing the value as a
> float would be able to impact the value itself (unless there is a
> problem with CCL's type inference).

What about when the integer is bigger than the biggest float
representable?

Floating point numbers go only up to very small number, like 10^646456992:

CL-USER> (values MOST-POSITIVE-SHORT-FLOAT MOST-POSITIVE-SINGLE-FLOAT
MOST-POSITIVE-DOUBLE-FLOAT MOST-POSITIVE-LONG-FLOAT)
3.4028s38
3.4028235E38
1.7976931348623157d308
8.8080652584198167656L646456992


10^646456992 is a small number it has only 646,456,992 digits! You can
easily compute bigger bignums.

And 32-bit IEEE-754 floats go only up to:

340282350000000000000000000000000000000

Which is a very small number! You only need 128 to represent it, that
is, it is a FIXNUM! Or could easily be a fixnum on a 128-bit
architecture. ;-)

[Tim Bradshaw]

Elias Mårtenson <lok...@gmail.com> wrote:

> That sounds very strange to me. Would you care to show the actual code?
>
> I can't think of any situation where just printing the value as a float
> would be able to impact the value itself (unless there is a problem with
> CCL's type inference).

FORMA coerces the number to a float in order to print it as one. See CLHS.

[Tim Bradshaw]

Tim Bradshaw <t...@tfeb.org> wrote:

> FORMA coerces the number to a float in order to print it as one. See CLHS.

Sorry: is allowed to convert.

[Espen Vestre]

"Pascal J. Bourguignon" <p...@informatimago.com> writes:

>> Yes, unless the number of arguments is quite limited (less than 50,
>> which is the lowest number that CALL-ARGUMENTS-LIMITS is allowed to have
>> according to the standard - on my 64 bit LW 6, it has the value 2047).
>
> Noot less than 50, less than CALL-ARGUMENTS-LIMIT, which can be quite
> high, eg in SBCL:

Well, I wrote "50, which is the lowest number that CALL-ARGUMENTS-LIMIT[S]
is allowed to have" (the rationale being that you get very *simple*
portable code by always avoiding #'apply if you know your lists may have
more than 50 elements).

> So if you suppose apply is faster than reduce, you could write:

Fair enough, but I think it's wise to add a caveat here: For most lisps
this will be useful only if you *really* need to optimize your code, and
which solution is the better isn't always very obvious - for instance,
LispWorks seems to do #'apply at least twice as fast as #'reduce - but
the latter doesn't cause the heavy consing that the former causes.
--
(espen)

[Helmut Eller]

* Pascal J. Bourguignon [2012-03-16 00:19] writes:

> Espen Vestre <es...@vestre.net> writes:
>
>> Jack <jack.m...@gmail.com> writes:
>>
>>> Is it considered better form to use reduce rather than apply?
>>
>> Yes, unless the number of arguments is quite limited (less than 50,
>> which is the lowest number that CALL-ARGUMENTS-LIMITS is allowed to have
>> according to the standard - on my 64 bit LW 6, it has the value 2047).
>
> Noot less than 50, less than CALL-ARGUMENTS-LIMIT, which can be quite
> high, eg in SBCL:
>
> % clall -r call-arguments-limit
> Armed Bear Common Lisp --> 50
> Clozure Common Lisp --> 65536
> CLISP --> 4096
> CMU Common Lisp --> 536870911
> ECL --> 65536
> SBCL --> 1152921504606846975
>
> So if you suppose apply is faster than reduce, you could write:

I doubt that you have any evidence that apply is ever faster than reduce.

>
> (if (< (length list) call-arguments-limit)
> (apply '+ list)
> (reduce '+ list))
>
> or even search on google groups for an older answer where I show how to
> group the elements in the list by call-arguments-limit to use apply as
> much as possible.

SBCL pushes arguments on the stack but the stack is much smaller than
CALL-ARGUMENTS-LIMIT and SBCL can't expand it automatically. So this
seem like a bad advice to me.

Helmut

[Espen Vestre]

Helmut Eller <eller....@gmail.com> writes:

> SBCL pushes arguments on the stack but the stack is much smaller than
> CALL-ARGUMENTS-LIMIT and SBCL can't expand it automatically. So this
> seem like a bad advice to me.

Hmm, that's interesting!

Another proof that the road to software hell is littered with premature
optimizations ;)
--
(espen)

[Tamas Papp]

I would say that there should be no disadvantages to using reduce all
the time, it's consistent and independent of implementation details.

I tend to think of * and + as convenience functions for reduce using
the respective binary operations. They fit so neatly into the syntax
of Lisp that we don't even notice this, as the binary versions are
just a special case.

Best,

Tamas

[Tim Bradshaw]

On 2012-03-16 09:56:30 +0000, Tamas Papp said:

> I would say that there should be no disadvantages to using reduce all
> the time, it's consistent and independent of implementation details.

FWIW the reason I used reduce in my followup is that it allowed me to
write my function more easily: it just needed two optional arguments
which defaulted to 1 rather than taking some list. I think the
equivalent applyable function would be

(lambda (l)
(apply #'* (mapcar #'round l)))

Which is not nearly as nice I think (and also: you could just replace
the call to apply to one to reduce!)

Of course the answer I gave didn't actually fix the problem, anyway...

[Elias Mårtenson]

Yeah, I realise now what had happened. My (mistaken) understanding when I wrote the post was that the error happened some time _after_ the call to FORMAT, and that removing that call also prevented the subsequent error.

As you rightfully pointed out, I never thought about the fact that ~F actually coerces (can coerce) the value to FLOAT.

[Tim Bradshaw]

On 2012-03-16 10:41:19 +0000, Elias Mårtenson said:
>
> As you rightfully pointed out, I never thought about the fact that ~F
> actually coerces (can coerce) the value to FLOAT.

SO, one thing I was wondering is this: it would be easy to say that
this is a quality-of-implementation issue, where the really shiny
implementations would not get an overflow because they'd do all sorts
of magic to avoid coercing something. But is that right, really? In
particular if an implementation gets a really big integer, what can it
usefully print for ~F?

[Kaz Kylheku]

I see, by the way, that you rightly balked at using the word "paved".

[Barry Margolin]

In article <jjv8jh$rl8$1...@dont-email.me>, Tim Bradshaw <t...@tfeb.org>
wrote:

It can simply print the integer followed by a decimal point and the
appropriate number of zeroes. If it's large enough that it would have
required exponential notation, it's simple to convert to that notation.

The recommendation to convert a rational to float is primarily aimed at
non-integer rationals. The algorithm for formatting the rational in
decimal point notation is probably not much different from converting it
to float, so you can just reuse it. But you could also use something
like the grade school long division algorithm to produce the decimal
notation, without converting it to float first.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Tim Bradshaw]

On 2012-03-16 17:06:52 +0000, Barry Margolin said:

> It can simply print the integer followed by a decimal point and the
> appropriate number of zeroes.

But that would not be readable if the number was bigger than a float
could be. I mean something like this:

(let* ((f (round most-positive-long-float))
(b (* f f)))
;; B is bigger than any floating type can be
(format nil "~F" b))

Obviously things are allowed to print B in a format that makes it look
like a float of some kind, but that looks a bit like digging a trap for
things that think they can read it as a float to fall into.

On the other hand it might be useful for people (ie the implementation
might be dealing in large integers but want to present them as floats
for readability by people).

[Pascal J. Bourguignon]

Helmut Eller <eller....@gmail.com> writes:

> * Pascal J. Bourguignon [2012-03-16 00:19] writes:
>
>> Espen Vestre <es...@vestre.net> writes:
>>
>>> Jack <jack.m...@gmail.com> writes:
>>>
>>>> Is it considered better form to use reduce rather than apply?
>>>
>>> Yes, unless the number of arguments is quite limited (less than 50,
>>> which is the lowest number that CALL-ARGUMENTS-LIMITS is allowed to have
>>> according to the standard - on my 64 bit LW 6, it has the value 2047).
>>
>> Noot less than 50, less than CALL-ARGUMENTS-LIMIT, which can be quite
>> high, eg in SBCL:
>>
>> % clall -r call-arguments-limit
>> Armed Bear Common Lisp --> 50
>> Clozure Common Lisp --> 65536
>> CLISP --> 4096
>> CMU Common Lisp --> 536870911
>> ECL --> 65536
>> SBCL --> 1152921504606846975
>>
>> So if you suppose apply is faster than reduce, you could write:
>
> I doubt that you have any evidence that apply is ever faster than reduce.

(reduce '+ list) will call (1- (length list)) times +. apply will call
it only once. Further, with apply, + has the opportunity to reorder the
argument which can give better and/or faster results.

>>
>> (if (< (length list) call-arguments-limit)
>> (apply '+ list)
>> (reduce '+ list))
>>
>> or even search on google groups for an older answer where I show how to
>> group the elements in the list by call-arguments-limit to use apply as
>> much as possible.
>
> SBCL pushes arguments on the stack but the stack is much smaller than
> CALL-ARGUMENTS-LIMIT and SBCL can't expand it automatically. So this
> seem like a bad advice to me.

In (apply '+ list) there are only two arguments.

[Helmut Eller]

* Pascal J. Bourguignon [2012-03-16 18:51] writes:

>> I doubt that you have any evidence that apply is ever faster than reduce.
>
> (reduce '+ list) will call (1- (length list)) times +. apply will call
> it only once.

I don't believe that. The obvious implementation of + with &rest args
loops over the &rest arg and calls a binary version of +. So in the end
apply also calls the binary + (1- (length list)) times. With the added
disadvantage that the list is first spread to the stack and then consed
up again as &rest list in some implementations.

> Further, with apply, + has the opportunity to reorder the
> argument which can give better and/or faster results.

apply is a function and arguments of functions are always evaluated from
left to right.

>> SBCL pushes arguments on the stack but the stack is much smaller than
>> CALL-ARGUMENTS-LIMIT and SBCL can't expand it automatically. So this
>> seem like a bad advice to me.
>
> In (apply '+ list) there are only two arguments.

SBCL transforms that to (multiple-value-call #'+ (values-list list)).
values-list pushes the entire list to the stack before calling #'+.
Just disassemble (lambda (list) (apply #'+ list)) to see the proof.

Helmut

[Paolo Micossi]

Helmut Eller <eller....@gmail.com> wrote:

> > Further, with apply, + has the opportunity to reorder the
> > argument which can give better and/or faster results.
>
> apply is a function and arguments of functions are always evaluated from
> left to right.

The single terms shall be evaluated left to right, but the order of
summation may be different from the order of evaluation. When you add
floats you often get a more accurate result (and never a less accurate
one) by summing the smaller terms first. A (smart) n-ary + can reorder
terms of such a sum to automagically optimize sum accuracy. Reducing a
binary + fixes the order of summation and does not offer such an option.
In an implementation optimized for numerics (apply #'+ terms) and
(reduce #'+ terms) might in fact give different results.
--
Paolo Micossi

[Helmut Eller]

OK that's true. By the same argument, reordering could also produce
less precise results. The result of reduce is more predictable.

Helmut

[Kaz Kylheku]

On 2012-03-16, Helmut Eller <eller....@gmail.com> wrote:
> * Pascal J. Bourguignon [2012-03-16 18:51] writes:
>> Further, with apply, + has the opportunity to reorder the
>> argument which can give better and/or faster results.
>
> apply is a function and arguments of functions are always evaluated from
> left to right.

Just a small note: order of evaluation of operands is not order of operations.