Re: [sage-devel] Re: Re: algdep (PARI) with clang on FreeBSD

[Thierry]

Hi,

On Thu, Mar 30, 2017 at 05:15:10PM +0200, Marc Mezzarobba wrote:
> Thierry wrote:
> > I found the reference i was looking for :
> > 
> http://doc.sagemath.org/html/en/reference/rings_numerical/sage/rings/real_double.html#sage.rings.real_double.RealDoubleElement.ulp
> 
> That the default rounding mode is round-to-nearest means that correctly 
> rounded results should be rounded to the nearest floating-point number 
> (as opposed to upwards, towards zero...), not necessarily that all 
> operations return correctly rounded results.
> 
> But you are right that in the particular case of sqrt(3), one would 
> expect the result to be correctly rounded, since the IEEE-754 standard 
> requires correct rounding for square roots, and processors usually 
> follow it...

Actually, the square root works with the correct rounding in RDF:

sage: RDF(3).sqrt().sign_mantissa_exponent()
(1, 7800463371553962, -52)

The issue here is the conversion from SR to RDF:

sage: RDF(sqrt(3)).sign_mantissa_exponent()
(1, 7800463371553963, -52)

Ciao,
Thierry


> 
> -- 
> Marc
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: making a reset() makes it impossible to "quit"

[jplab]

Thanks for the pointer!

Le jeudi 30 mars 2017 11:37:32 UTC+2, Frédéric Chapoton a écrit :
>
> https://trac.sagemath.org/ticket/22529
>
> Le jeudi 30 mars 2017 11:07:22 UTC+2, jplab a écrit :
>>
>>
>>
>> Le mercredi 29 mars 2017 19:48:57 UTC+2, John H Palmieri a écrit :
>>>
>>> It looks like a bug to me.
>>>
>>>
>> Should I open a ticket then? 
>>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Re: algdep (PARI) with clang on FreeBSD

[Marc Mezzarobba]

Thierry wrote:
> I found the reference i was looking for :
> 
http://doc.sagemath.org/html/en/reference/rings_numerical/sage/rings/real_double.html#sage.rings.real_double.RealDoubleElement.ulp

That the default rounding mode is round-to-nearest means that correctly 
rounded results should be rounded to the nearest floating-point number 
(as opposed to upwards, towards zero...), not necessarily that all 
operations return correctly rounded results.

But you are right that in the particular case of sqrt(3), one would 
expect the result to be correctly rounded, since the IEEE-754 standard 
requires correct rounding for square roots, and processors usually 
follow it...

-- 
Marc

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] algdep (PARI) with clang on FreeBSD

[Jeroen Demeyer]

On 2017-03-29 11:24, Dima Pasechnik wrote:

Is the following a bug, or  not:


Fix planned at
https://trac.sagemath.org/ticket/22714

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: algdep (PARI) with clang on FreeBSD

[Vincent Delecroix]

On 30/03/2017 11:33, Thierry wrote:

Hi,

On Thu, Mar 30, 2017 at 10:20:21AM +0200, Marc Mezzarobba wrote:

Thierry wrote:

I do not remember where i read that (correct me if i am wrong, or
provide a reference if you know where it is), but RDF is supposed to
round towards the nearest floating-point number.


RR is, but I think RDF may or may not provide correct rounding depending
what the underlying libm does.


I found the reference i was looking for :
http://doc.sagemath.org/html/en/reference/rings_numerical/sage/rings/real_double.html#sage.rings.real_double.RealDoubleElement.ulp

So, if this depends on libm, i guess this should be updated and we should
provide a way to know/modify the current rounding mode ?


You can obtain and modify the CPU rounding mode using the C functions 
declared in fenv.h


int FE_TONEAREST
int FE_UPWARD
int FE_DOWNWARD
int FE_TOWARDZERO
int fegetround ()
int fesetround (int)

(there is an example in src/sage/graphs/base/static_sparse_graph.pyx)

However, this go beyond libm and will affect any library using floating 
point numbers.


Vincent

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: making a reset() makes it impossible to "quit"

[Frédéric Chapoton]

https://trac.sagemath.org/ticket/22529

Le jeudi 30 mars 2017 11:07:22 UTC+2, jplab a écrit :
>
>
>
> Le mercredi 29 mars 2017 19:48:57 UTC+2, John H Palmieri a écrit :
>>
>> It looks like a bug to me.
>>
>>
> Should I open a ticket then? 
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: algdep (PARI) with clang on FreeBSD

[Thierry]

Hi,

On Thu, Mar 30, 2017 at 10:20:21AM +0200, Marc Mezzarobba wrote:
> Thierry wrote:
> > I do not remember where i read that (correct me if i am wrong, or
> > provide a reference if you know where it is), but RDF is supposed to
> > round towards the nearest floating-point number.
> 
> RR is, but I think RDF may or may not provide correct rounding depending 
> what the underlying libm does.

I found the reference i was looking for :
http://doc.sagemath.org/html/en/reference/rings_numerical/sage/rings/real_double.html#sage.rings.real_double.RealDoubleElement.ulp

So, if this depends on libm, i guess this should be updated and we should
provide a way to know/modify the current rounding mode ?

Ciao,
Thierry



> -- 
> Marc
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an 
> email to sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: making a reset() makes it impossible to "quit"

[jplab]

Le mercredi 29 mars 2017 19:48:57 UTC+2, John H Palmieri a écrit :
>
> It looks like a bug to me.
>
>
Should I open a ticket then? 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: algdep (PARI) with clang on FreeBSD

[Marc Mezzarobba]

Thierry wrote:
> I do not remember where i read that (correct me if i am wrong, or
> provide a reference if you know where it is), but RDF is supposed to
> round towards the nearest floating-point number.

RR is, but I think RDF may or may not provide correct rounding depending 
what the underlying libm does.

-- 
Marc

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-combinat-devel] Re: Improvements to FreeAlgebra

[Simon King]

Hi Nicolas,

On 2017-03-29, Nicolas M. Thiery  wrote:
> It would be interesting to know specifically on which aspects the path
> algebra is improving on the current free algebra. The data structure
> of indices (i.e. words in the generators)? The data structure for
> representing linear combinations? The implementation of the product?
>
> Maybe some of those improvements could be lifted up to FreeModule in
> the first place, or provide an alternative generic implementation of
> it that would work better for your use case [1].

My own use case is proper path algebras with *several* vertices. So,
FreeModule won't cover my own applications.

My comment was motivated by a question on sage-support. The question
has merely been about the fact that 1 is not recognised as an element 
of a free algebra over ZZ, and while trying to give the user some 
work-arounds, I played with different ways to create what mathematically 
is a free associative algebra.

Why is it faster?
1. Paths are implemented as BoundedIntegerSequences, which in turn
   are implemented as bitsets. Concatenation ultimately relies on
   bitshift operations, that are quite efficiently implemented in
   MPR.
2. Path algebra elements are implemented as ordered chain of terms
   ("chain" as in "a term is a C struct that has a pointer to
   the next term").

You can of course easily benefit from using 1. for the indices.
If you have n generators, then your indices simply are sequences 
of integers bounded by n.
- Multiplication is list concatenation, which is faster than for 
  Python tuples and (if I recall correctly) even faster than operations 
  that are based on implementing integer sequences as C "*int".
- CombinatorialFreeModule.Element is (IIRC) implemented as dictionary,
  where the indices are used as keys. BoundedIntegerSequence is
  faster than python tuples both in hash and comparison (in particular
  if the tuples have common starting sequences).

Examples:

sage: L1 = tuple(randint(0,49) for _ in range(1000))
sage: L2 = tuple(randint(0,49) for _ in range(1000))
sage: from sage.data_structures.bounded_integer_sequences import 
BoundedIntegerSequence
sage: BL1 = BoundedIntegerSequence(50, list(L1))
sage: BL2 = BoundedIntegerSequence(50, list(L2))
sage: %timeit BL1+BL2
100 loops, best of 3: 312 ns per loop
sage: %timeit L1+L2
10 loops, best of 3: 4.16 µs per loop
sage: %timeit hash(BL1)
1000 loops, best of 3: 83.5 ns per loop
sage: %timeit hash(L1)
10 loops, best of 3: 3.34 µs per loop
sage: CBL1 = BoundedIntegerSequence(50, list(L1))
sage: %timeit BL1==BL2
1000 loops, best of 3: 66.8 ns per loop
sage: %timeit BL1==CBL1
1000 loops, best of 3: 124 ns per loop
sage: CL1 = tuple(list(L1))
sage: %timeit L1==L2
1000 loops, best of 3: 53.8 ns per loop
sage: %timeit L1==CL1
10 loops, best of 3: 4.83 µs per loop

In fact, this is what has been done in an earlier implementation of
path algebras. However, 2. is still faster than an implementation that
expresses elements as dictionaries. But I guess you don't want
an implementation of CombinatorialFreeModuleElementWithMonomialOrdering.

Best regards,
Simon

-- 
You received this message because you are subscribed to the Google Groups 
"sage-combinat-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-combinat-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-combinat-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-combinat-devel.
For more options, visit https://groups.google.com/d/optout.