Re: [fricas-devel] Algebraic Topology Issue 1
Hello Martin As promised (before vacation) below two examples which I'm unable to interpret (otherwise I recognized that you've improved your code and that it's now included in fricas -- great :). A lot more examples work now (i.e same results as Kenzo). BTW: why didn't you allow '0'? NNI=0,1,2,... ;) -- from https://www-fourier.ujf-grenoble.fr/~sergerar/Kenzo/Kenzo-doc.pdf --- ASIMP := FiniteSimplicialComplex(VertexSetAbstract) v0:List(List(NNI)) :=[[0],[1],[2],[3],[4],[5],[6],[7], _ [0,1],[0,2],[0,3], _ [0,4],[0,5],[0,6], _ [0,7],[1,2],[1,3], _ [1,4],[1,5],[1,6], _ [1,7],[2,3],[2,4], _ [2,6],[2,7],[3,4], _ [3,5],[4,5],[4,6], _ [5,6],[5,7],[6,7], _ [0,1,5],[0,1,6],[0,1,7], _ [0,2,3],[0,2,4],[0,2,6], _ [0,3,4],[0,5,7],[1,2,3], _ [1,2,4],[1,2,7],[1,3,5], _ [1,4,6],[2,6,7],[3,4,5], _ [4,5,6],[5,6,7]] -- Dunce hat -- https://en.wikipedia.org/wiki/Dunce_hat_(topology) v1:List(List(NNI)) :=[[1],[2],[3],[4],[5],[6],[7],[8], _ [1,2],[1,3],[1,4], _ [1,5],[1,6],[1,7], _ [1,8],[2,3],[2,4], _ [2,5],[2,6],[2,7], _ [2,8],[3,4],[3,5], _ [3,7],[3,8],[4,5], _ [4,6],[5,6],[5,7], _ [6,7],[6,8],[7,8], _ [1,2,6],[1,2,7],[1,2,8], _ [1,3,4],[1,3,5],[1,3,7], _ [1,4,5],[1,6,8],[2,3,4], _ [2,3,5],[2,3,8],[2,4,6], _ [2,5,7],[3,7,8],[4,5,6], _ [5,6,7],[6,7,8]] dunceHat := simplicialComplex(vertexSeta(8::NNI),v1)$ASIMP homology dunceHat -- [Z,Z*24,0] , actually H0=Z, others 0. -- Diabolo v2:List(List(NNI)) := [[1],[2],[3],[4],[5],[6], _ [1,2],[1,3],[2,3],[3,4],[4,5],[4,6],[5,6], _ [4,5,6]] diabolo:= simplicialComplex(vertexSeta(6::NNI),v2)$ASIMP homology diabolo -- [Z,Z*4,0] , actually H0=Z, H1=Z, H2=0. Am 06.09.2016 um 11:24 schrieb Martin Baker: > Martin B > Kurt -- 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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] IndexedList
On 09/18/2016 04:26 PM, oldk1331 wrote: > My point is, for List, one should not use index to get its element, > because it's O(n) to do index. In C++, std::list does not have > operator[], "all STL sequences that support operator[] should > do it in amortized constant time". > I would even suggest we do the same, domains that export > IndexedAggregate must have constant time elt(%, n). Cool. You hit a point that I would also love to see. No, for computations it is not enough if a function documentation says something about what the function does, i.e., input/output behaviour. It is also important to say something about the complexity of the implementation. Yes, it is sometimes good to have functionality that maybe inefficient in a certain implementation (like indexing in lists). That would allow for easier prototyping where it is not yet clear how the final (most efficient data structure will look like. But I am very much in favour of having some functionality that says something about its complexity. So one could have elt: .. -> .. and constantTimeElt: .. -> .. (I just made up the name) and the latter would only be exported if the implementtion assures that access is O(1). Or, we introduce separate categories for this (maybe something like ConstantTimeElementAccess). I'm open for discussion. Ralf -- 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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] Minor code changes to computation.spad
Martin Baker wrote:
>
> Thanks for applying previous patch.
>
> When you did this you made some changes and one of these changes
> introduced a bug, so here is a fix for this bug:
I got caught by Spad weirdness. In Spad
"string"::OutputForm
is the same as
"string"@OutputForm
which gives the same result as
message("string")
that is without string quotes. OTOH
ss : String := "string"
ss::OutputForm
is the same as interpreter "string"::OutputForm and adds
string quote. I am thinking about removing the special
handling of '"string"@OutputForm' from Spad compiler.
There seem to be several uses of this in algebra, so there
is some work adjusting. But still I think that removing this
irregularity is better.
--
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 fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
oldk1331 wrote: > > > Also, there is tricky balance > > between speed and code size: for rarely executed code > > the main cost is reading it from RAM and evicting > > from cache more useful code. That can negate gains > > from faster execution. > > Well, MAKELIST$Lisp is surely most RAM efficient and > fastest. I was probably unclear: code size matters in case of list comprehension because each use is a separate copy of a template and there are a lot of uses in the algebra. Also, on my machine the following version: new(n, e) == res := empty() for i in 1..n repeat res := cons(e, res) res which produces result in "reverse" order for long lists has the same speed (within measurement noise) as MAKELIST version. For short list it may be faster, because 'make-list' probably have few extra instructions to parse keyword arguments. Concerning RAM efficient: the version above is probably of smaller than 'make-list'. Of course 'make-list' is already contained in Lisp image, but code that we do not use at all is cheap: there is resonable chance that it will live only on disc and almost surely will not get into caches. > I want to know when it's worth to introduce a > Lisp function instead of implement it in Spad? Well some Lisp functions are "primitives", they offer functionalty which is not available in other way. Of course we need them. Then there are functions which we introduce for performance. In particular Spad compiler will only inline functions which have single Lisp expression as implementation. So if some operation should be inlined it has to be implemented via call to Lisp macro/function. Now, basically all functions could get some speedup by providing optimized Lisp implementation. But if you look at hand-written Lisp code you will see that most is less optimized than code generated by Spad compiler. Simply most of code is not performance critical. So for most code clarity and correctness are much more important. Now, for typical Spad programmer Lisp code is an opaque blob and hence less clear than Spad code. So write in Spad unless you have strong reason to use Lisp. That is there is significant speed gain or using Lisp function say saves effort to rewrite some substaial piece of code. Note: speed gain of 10% in rarely used function is insignifcant. Gain of 10% in freqently used function is worthwile, but it is not always clear if gain is real and robust. That is there may be gain on benchmarks but no gain (or even loss) in real use. As an example, in the past two dimensional Spad arrays were implemented as PrimitiveArray of PrimitiveArray-s and element accessors were Spad functions. Replacing Spad code by Lisp macros gave about 20 times faster array accessors. Given that array accessors are frequently used in inner loops this was a clear gain. -- 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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] IndexedList
> IndexedList is useful if somebody wants to port code which > uses differernt indexing. My point is, for List, one should not use index to get its element, because it's O(n) to do index. In C++, std::list does not have operator[], "all STL sequences that support operator[] should do it in amortized constant time". I would even suggest we do the same, domains that export IndexedAggregate must have constant time elt(%, n). -- 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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
> Also, there is tricky balance > between speed and code size: for rarely executed code > the main cost is reading it from RAM and evicting > from cache more useful code. That can negate gains > from faster execution. Well, MAKELIST$Lisp is surely most RAM efficient and fastest. I want to know when it's worth to introduce a Lisp function instead of implement it in Spad? -- 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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] [PATCH] make new$List faster
oldk1331 wrote: > > BTW2: If you are worried that [...] is slower than > > MAKELIST you should rather work on increasing speed > > of list comprehesion (that is []). Current > > version constructs list in reverse order and then > > destructively reverses the result. > > It is possible to avoid the NREVERSE call? > Unless you do it by recursion and risk the stack > to explode? Well, for 'new' formally the final NREVERSE is not needed at all since all nodes have the same value. In general there is well-know imperative idiom: after creating next node one updates previous node. Essentially: new(n, e) == e0 := empty() n = 0 => e0 res := cons(e, e0) old := res for i in 2..n repeat new := cons(e, old) setrest!(old, new) new := old res As you see the code is longer than version working in reverse. For long list avoidning second scan should give small win. For short lists (most important case) that is more tricky: one needs to make sure that the code (in particular loop setup) is well optimized to have any gain. Also, there is tricky balance between speed and code size: for rarely executed code the main cost is reading it from RAM and evicting from cache more useful code. That can negate gains from faster execution. -- 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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
Re: [fricas-devel] IndexedList
oldk1331 wrote: > What's your opinion on removing IndexedList? IndexedList is useful if somebody wants to port code which uses differernt indexing. Sure, speed will be suboptimal, but frequently minimizing coding effort wins. And given that Common Lisp uses 0-based indexing there is substantial body of code that one may wish to port. -- 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 fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
