Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #14471 > unrolled thread
| Started by | "djmpark" <djmpark@comcast.net> |
|---|---|
| First post | 2013-05-12 07:28 +0000 |
| Last post | 2013-06-04 03:14 +0000 |
| Articles | 3 on this page of 83 — 28 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
Work on Basic Mathematica Stephen! "djmpark" <djmpark@comcast.net> - 2013-05-12 07:28 +0000
Re: Work on Basic Mathematica Stephen! psycho_dad <s.nesseris@gmail.com> - 2013-05-13 07:47 +0000
Re: Work on Basic Mathematica Stephen! psycho_dad <s.nesseris@gmail.com> - 2013-05-13 09:40 +0000
Re: Work on Basic Mathematica Stephen! "Nasser M. Abbasi" <nma@12000.org> - 2013-05-14 07:14 +0000
Re: Work on Basic Mathematica Stephen! Szabolcs Horvát <szhorvat@gmail.com> - 2013-05-15 06:54 +0000
Re: Work on Basic Mathematica Stephen! Szabolcs Horvát <szhorvat@gmail.com> - 2013-05-16 07:28 +0000
Re: Work on Basic Mathematica Stephen! Peter Klamser <klamser@googlemail.com> - 2013-05-16 07:28 +0000
Re: Work on Basic Mathematica Stephen! Andrzej Kozlowski <akozlowski@gmail.com> - 2013-05-17 08:34 +0000
Re: Work on Basic Mathematica Stephen! Murray Eisenberg <murray@math.umass.edu> - 2013-05-17 08:34 +0000
Re: Work on Basic Mathematica Stephen! Peter Klamser <klamser@googlemail.com> - 2013-05-17 08:34 +0000
Re: Work on Basic Mathematica Stephen! Andrzej Kozlowski <akozlowski@gmail.com> - 2013-05-18 06:38 +0000
Re: Work on Basic Mathematica Stephen! Peter Klamser <klamser@googlemail.com> - 2013-05-18 06:37 +0000
Re: Work on Basic Mathematica Stephen! Murray Eisenberg <murray@math.umass.edu> - 2013-05-19 09:46 +0000
Re: Work on Basic Mathematica Stephen! paulmchale7@gmail.com - 2013-05-19 09:47 +0000
Re: Work on Basic Mathematica Stephen! paulmchale7@gmail.com - 2013-05-19 09:47 +0000
Re: Work on Basic Mathematica Stephen! Szabolcs Horvát <szhorvat@gmail.com> - 2013-05-23 07:51 +0000
Re: Work on Basic Mathematica Stephen! "djmpark" <djmpark@comcast.net> - 2013-05-24 09:26 +0000
Re: Work on Basic Mathematica Stephen! ?iso-8859-1?Q?J=E1nos_L=F6bb?= <janos@lobb.com> - 2013-05-19 09:47 +0000
Re: Work on Basic Mathematica Stephen! Andrzej Kozlowski <akozlowski@gmail.com> - 2013-05-20 09:03 +0000
Re: Work on Basic Mathematica Stephen! Andrzej Kozlowski <akozlowski@gmail.com> - 2013-05-20 09:03 +0000
Re: Work on Basic Mathematica Stephen! "Ernst H.K. Stelzer" <ernst.stelzer@physikalischebiologie.de> - 2013-05-20 09:03 +0000
Re: Work on Basic Mathematica Stephen! Ingolf Dahl <ingolf.dahl@telia.com> - 2013-05-20 09:03 +0000
Re: Work on Basic Mathematica Stephen! David Annetts <david.annetts@iinet.net.au> - 2013-05-20 09:03 +0000
Re: Work on Basic Mathematica Stephen! "mathgroup " <fizzymath@knology.net> - 2013-05-22 06:18 +0000
expanding the use of symbolic computation in engineering .. was Re: Richard Fateman <fateman@cs.berkeley.edu> - 2013-05-23 07:51 +0000
Re: expanding the use of symbolic computation in engineering .. was Re: W Craig Carter <ccarter@MIT.EDU> - 2013-05-24 09:23 +0000
Re: Work on Basic Mathematica Stephen! "djmpark" <djmpark@comcast.net> - 2013-05-23 07:54 +0000
Re: Work on Basic Mathematica Stephen! "mathgroup " <fizzymath@knology.net> - 2013-05-23 07:56 +0000
Re: Work on Basic Mathematica Stephen! Richard Fateman <fateman@cs.berkeley.edu> - 2013-05-24 09:27 +0000
Re: Work on Basic Mathematica Stephen! "djmpark" <djmpark@comcast.net> - 2013-05-25 09:35 +0000
Re: Work on Basic Mathematica Stephen! Richard Fateman <fateman@eecs.berkeley.edu> - 2013-05-25 09:35 +0000
Re: Work on Basic Mathematica Stephen! "djmpark" <djmpark@comcast.net> - 2013-05-25 09:35 +0000
Re: Work on Basic Mathematica Stephen! "mathgroup " <fizzymath@knology.net> - 2013-05-24 09:28 +0000
Re: Work on Basic Mathematica Stephen! Murray Eisenberg <murray@math.umass.edu> - 2013-05-24 09:23 +0000
Re: Work on Basic Mathematica Stephen! "djmpark" <djmpark@comcast.net> - 2013-05-24 09:26 +0000
Re: Work on Basic Mathematica Stephen! Andrzej Kozlowski <akozlowski@gmail.com> - 2013-05-25 09:34 +0000
Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Richard Fateman <fateman@cs.berkeley.edu> - 2013-05-26 08:38 +0000
more problems in Warsaw plan? Re: Work on Basic Mathematica Stephen! Richard Fateman <fateman@cs.berkeley.edu> - 2013-05-26 08:36 +0000
Re: Work on Basic Mathematica Stephen! David Bailey <dave@removedbailey.co.uk> - 2013-05-28 07:47 +0000
Re: Work on Basic Mathematica Stephen! John Doty <noqsiaerospace@gmail.com> - 2013-05-27 08:21 +0000
Re: Work on Basic Mathematica Stephen! David Bailey <dave@removedbailey.co.uk> - 2013-06-02 04:24 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! John Doty <noqsiaerospace@gmail.com> - 2013-05-27 08:21 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Richard Fateman <fateman@cs.berkeley.edu> - 2013-05-28 07:49 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! David Bailey <dave@removedbailey.co.uk> - 2013-05-31 07:19 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-01 10:06 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! David Bailey <dave@removedbailey.co.uk> - 2013-06-02 04:22 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-03 07:25 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! David Bailey <dave@removedbailey.co.uk> - 2013-06-04 03:14 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Andrzej Kozlowski <akozlowski@gmail.com> - 2013-06-04 09:59 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Richard Fateman <fateman@eecs.berkeley.edu> - 2013-06-04 03:15 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Ingolf Dahl <ingolf.dahl@telia.com> - 2013-05-27 08:21 +0000
Re: Work on Basic Mathematica Stephen! fd <fdimer@gmail.com> - 2013-05-28 07:46 +0000
Re: Work on Basic Mathematica Stephen! David Bailey <dave@removedbailey.co.uk> - 2013-05-31 07:19 +0000
Re: Work on Basic Mathematica Stephen! fd <felipe.dimer-de-oliveira@mq.edu.au> - 2013-05-28 07:47 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! fd <fdimer@gmail.com> - 2013-05-29 07:47 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Andrzej Kozlowski <akozlowski@gmail.com> - 2013-05-29 07:48 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! János Löbb <janos@lobb.com> - 2013-05-30 10:07 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! "Nasser M. Abbasi" <nma@12000.org> - 2013-05-31 07:15 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Mathematica Stephen! Murray Eisenberg <murray@math.umass.edu> - 2013-05-30 10:08 +0000
Applying Mathematica to practical problems John Doty <noqsiaerospace@gmail.com> - 2013-05-30 10:09 +0000
Re: Applying Mathematica to practical problems Richard Fateman <fateman@cs.berkeley.edu> - 2013-05-31 07:15 +0000
Re: Applying Mathematica to practical problems "Kevin J. McCann" <kjm@KevinMcCann.com> - 2013-05-31 07:18 +0000
Re: Applying Mathematica to practical problems Andrzej Kozlowski <akozlowski@gmail.com> - 2013-05-31 07:16 +0000
Re: Applying Mathematica to practical problems Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-01 10:07 +0000
Re: Applying Mathematica to practical problems Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-01 10:07 +0000
Re: Applying Mathematica to practical problems Andrzej Kozlowski <akozlowski@gmail.com> - 2013-06-02 04:23 +0000
Re: Applying Mathematica to practical problems Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-03 07:24 +0000
Re: Applying Mathematica to practical problems Andrzej Kozlowski <akozlowski@gmail.com> - 2013-06-04 03:11 +0000
Re: Applying Mathematica to practical problems Andrzej Kozlowski <akozlowski@gmail.com> - 2013-06-04 03:11 +0000
Re: Applying Mathematica to practical problems Richard Fateman <fateman@eecs.berkeley.edu> - 2013-06-04 03:10 +0000
Re: Applying Mathematica to practical problems Andrzej Kozlowski <akozlowski@gmail.com> - 2013-06-04 03:11 +0000
Re: Applying Mathematica to practical problems Andrzej Kozlowski <akozlowski@gmail.com> - 2013-06-04 03:13 +0000
Mathematica numerics and... Re: Applying Mathematica to practical problems Daniel Lichtblau <danl@wolfram.com> - 2013-06-01 10:06 +0000
Interval vs default, was Re: Mathematica numerics and... Re: Applying Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-02 04:24 +0000
Re: Applying Mathematica to practical problems Andrzej Kozlowski <akozlowski@gmail.com> - 2013-06-02 04:23 +0000
Re: Applying Mathematica to practical problems James Stein <mathgroup@stein.org> - 2013-06-02 04:26 +0000
Re: Applying Mathematica to practical problems Mark McClure <mcmcclur@unca.edu> - 2013-06-02 04:23 +0000
Re: Applying Mathematica to practical problems Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-03 07:25 +0000
Re: Applying Mathematica to practical problems Joe Gwinn <joegwinn@comcast.net> - 2013-06-03 07:26 +0000
Re: Applying Mathematica to practical problems Waclaw Kusnierczyk <waku@idi.ntnu.no> - 2013-06-03 07:24 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Leonid Shifrin <lshifr@gmail.com> - 2013-06-04 03:12 +0000
Re: Warsaw Univ. course, was Re: Work on Basic Leonid Shifrin <lshifr@gmail.com> - 2013-06-04 03:13 +0000
Re: Interval vs default, was Re: Mathematica numerics and... Re: Applying Daniel Lichtblau <danl@wolfram.com> - 2013-06-04 03:14 +0000
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | Leonid Shifrin <lshifr@gmail.com> |
|---|---|
| Date | 2013-06-04 03:12 +0000 |
| Subject | Re: Warsaw Univ. course, was Re: Work on Basic |
| Message-ID | <kojlva$kas$1@smc.vnet.net> |
| In reply to | #14471 |
On Tue, Jun 4, 2013 at 12:45 AM, Richard Fateman
<fateman@eecs.berkeley.edu>wrote:
> On 6/3/2013 9:25 AM, Leonid Shifrin wrote:
>
> <long message>
>
> Thanks for what I consider a most agreeable contribution.
> I was not aware of your material on stackexchange, which seems
> to be rather nice.
>
Thanks, I do appreciate your opinion.
>
>
> You are right that my example regarding mutable Lists in Mathematica
> was incorrect. Actually on two grounds. The syntax was not right and
> I did not mean to say that Lists in Mathematica are not mutable, since
> they certainly are.
>
> Just that Lists have the uncomfortable property that if you access one
> element,
> all the others are re-evaluated. Here is an example, which I think is free
> of
> mis-used syntax...
>
> ( q=Table[f[i],{i,1,3}];
> f[n_]:=(Print[n];g[n]))
>
> q[[2]]
>
> evaluates to display
> 1
> 2
> 3
> g[2]
>
> Changing q by, for example, q[[2]]=hello
> does not re-evaluate the elements.
> However, referring to in again as q[[2]] does this:
> 1
> 3
> hello
>
Yes, this is indeed what happens. Arguably this is a correct behavior
(for Mathematica), because Mathematica can not tell in advance that
q will not evaluate to something else. For example, we could have q
assigned to some other symbol, and that symbol to hold the list.
In general, this is because Part does not hold its arguments. Given that
Part works on general expressions, I don't find this inconsistent.
If you don't want this behavior, one way out is to not store the values in
a list, but rather store them in some head which holds their elements,
such as Hold:
In[5]:= q1 = Map[f, Hold @@ Range[3]]
Out[5]= Hold[f[1], f[2], f[3]]
In this case, we get
In[6]:= q1[[2]]
During evaluation of In[6]:= 2
Out[6]= g[2]
Which seems to be the behavior you expected. One could
use HoldComplete in place of Hold, which would arguably
be even better since that would have prevented any non-trivial
evaluation of q1 whasoever (including e.g. search for UpValues,
not prevented by Hold).
Regards,
Leonid
>
> Thanks for pointing out the original error.
> RJF
>
>
>
[toc] | [prev] | [next] | [standalone]
| From | Leonid Shifrin <lshifr@gmail.com> |
|---|---|
| Date | 2013-06-04 03:13 +0000 |
| Subject | Re: Warsaw Univ. course, was Re: Work on Basic |
| Message-ID | <kojm17$kbi$1@smc.vnet.net> |
| In reply to | #14471 |
> I have no objection to a data type that might reasonably be called
> Vector, or perhaps Sequence, that implements a data structure that uses
> sequential storage. I object to calling it List.
>
I'd probably agree with this. But it is too late by now, in any case.
> >
> > Try using your implementation to implement some 1000 x 1000 matrix
> algebra!
>
> I would not particularly advise using linked lists for a dense matrix,
> but linked lists for small matrices might be just fine, or sparse
> matrices of large dimension but few entries. In the context of SYMBOLIC
> matrices, one generally ends up using smallish sizes because of
> explosive growth in costs for doing non-trivial operations with them.
> In a numeric context, 1000x1000 or much much larger is more likely.
>
> >
> > OK - perhaps you wouldn't want to use your new list implementation for
> > linear algebra, but in that case, where would you want to use it?
>
> You think that linked lists are of no use? If you have access to
> a computer science text on data structures, I suggest you look. Or
> use Google for ... applications linked lists.
>
> > Lisp
> > lists are expensive to use unless the algorithm is tailored to generate
> > lists in reverse order, and consume them in forward order (OK you can
> > reverse a Lisp list, but that consumes space for a copy, but random
> > access is still inefficient).
>
> This is a silly argument. If you know in advance that the size of a
> vector is n then you can allocate space for it in Mathematica or in Lisp
> as a vector.
> If you don't know the size,
> adding one more element beyond the allocated space n requires O(n)
> time for copying. For a linked list it is O(1) to add an element.
> This has consequences for many applications including building queues,
> algebraic expression trees, storage management etc. Perhaps you are
> familiar with the related notion of a pointer, in the C language.
>
> It is quite possible to write a lisp program that appends to the end of
> a list in time O(1). If you have access to information on lisp, look up
> nconc. It is, however a "destructive" operation, and not my favorite
> way of building a list. If I want to reverse a list that I know is not
> shared (i.e. I just constructed it!) I can use nreverse which is
> quite fast, and reverses a list IN PLACE. Accessing elements in a linked
> list of just a few elements (say, 8 or 10?) may be faster than accessing
> elements in a vector, where array indexes may have to be translated into
> byte addresses, checked against array bounds, before retrieving.
> Note that once a linked list is stored in memory cache, accesses can be
> quite fast.
>
> If a lisp programmer wants to use an array, that is available in the
> language. If a lisp programmer wants to use a linked list, that is
> available too. If a Mathematica programmer wants to use a linked list,
> there is the (admittedly clumsy) construction I suggested previously,
> but basically it not an advertised option.
>
Well, I'd say it can be used quite successfully. Here is a recent post I've
made where I tried to summarize my and others' experiences with these
constructs:
http://mathematica.stackexchange.com/questions/24988/can-one-identify-the-design-patterns-of-mathematica/25474#25474
In particular, there I mentioned two less trivial problems where linked
lists were particularly beneficial in the Mathematica context:
http://mathematica.stackexchange.com/questions/5387/how-can-i-use-mathematicas-graph-functions-to-cheat-at-boggle/5394#5394
and
http://mathematica.stackexchange.com/questions/6704/performance-tuning-for-game-solving-peg-solitaire-senku/6891#6891
The real problem is that Mathematica is a laguage of multiple performance scales. There is a scale associated with the top-level code (pretty slow), there is a scale associated with the pattern-matching (can be order of magnitude faster if the patterns are constructed right), and there is a scale associated with packed arrays and vectorized operations, which is yet an order or even two orders of
magnitude faster.
At the same time, Mathematica does not possess general performant data structures (in the sense in which C or Java or e.g. SML, or Lisp, have them). So, one is often forced to shoehorn the problem's code into a set of efficient data structures it has (packed arrays, sparse arrays). While there are a number of techniques available to achieve this, and I tried to summarize those known to me here
http://stackoverflow.com/questions/4721171/performance-tuning-in-mathematica/4723969#4723969
I would agree that for many problems this may lead to rather unnatural and twisted code. The biggest problem with this is that one has to have near expert-level skills to be able to work effectively with this for *any* problem.
OTOH, for many data processing problems, Mathematica's approach of "work
with as much data at once as possible" also has an advantage that it allows
a very high-level thinking and very concise *and* reasonably fast code - a
feature probably borrowed conceptually from APL. So, many intermediate
users who have mastered vectorized subset of Mathematica can be extremely
effective with their work without actually becoming professional
programmers. In other words, the vectorized susbset of Mathematica combined
with its very high-level nature and great visualization capabilities
constitutes IMO a very effective and rather easy to use DSL.
So, this looks to be a double-edged sword. I think that the actual problem
is to find a right balance,given that the vast majority of Mathematica
users are not professional programmers and do not intend to become ones.
Your criticism has a lot of valid points from a CS viewpoint, but I don't
think that this viewpoint is the most important one for the majority of
users. And this seems to be what others were telling here, in different
words.
Returning to linked lists, they can still give some of the best top-level
performance possible in Mathematica without using packed arrays, sparse
arrays, Compile and other techniques which would constrain the types of
data for which they can be applied. In some cases, Mathematica is flexible
enough to make up for this gap (to some extent). Here is a link to one such
example, where I implemented a version of merge function for the merge sort
algorithm, which uses linked lists for general case and automatically
creates JIT-compiled memoized versions for numerical data:
http://mathematica.stackexchange.com/questions/6931/implementing-a-function-which-generalizes-the-merging-step-in-merge-sort/6933#6933
So, let me put it this way: Mathematica seems to be a good compromise
between being practical and having flawless language design (considered
from a pure CS viewpoint), and as a language designed to be used by not
professional programmers, does quite well in many practical cases. If we
consider its design from the practical viewpoint of the majority of its
current heavy users, its design is probably close to optimal however.
>
> If you want to look for ways in which lisp can be expensive, I
> suggest you learn more about it, for example understanding boxed/unboxed
> numbers.
>
> The idea that someone might write a slow program in a language
> is not an indictment of the language if a slightly more experienced or
> skilled or knowledgeable person could write an equivalent computation
> that runs very fast. It would be nice if even naive programs written
> by naive programmers were magically "optimized" into better programs.
> This is a challenge in the design and implementation of languages.
>
Yes, I agree with this, but for Mathematica, the other path was chosen - to
make
it practical first. That means make a few reasonably well-designed DSL-s
for practical things, and make sure they can be glued together without
many semantic inconsistencies. That's what Mathematica currently does.
And I don't exclude that in the future, things will get more optimized
(e.g. Compile will be able to handle a wider subset of Mathematica), and
some useful things may be added to the language. The model of computation
of Mathematica is very general, so it may be able to accommodate new
additions to the language.
> E.g. "automatic parallelization" ...
>
> My criticisms of Mathematica's language (EF) are
> based on situations in which the language itself interferes with the
> writing of efficient or mathematically consistent or even numerically
> accurate programs. And it misuses names...
>
You are clearly speaking from the CS viewpoint here. It may be not the
only valid point of view.
>
> >
> > Mathematica also gains from the decision to make lists mutable - again
> > this simplifies the design of algorithms and increases performance.
>
> I have no idea what you are arguing about. Lists in lisp are mutable.
> e.g. (setf x '(a b c)) (setf (second x) 'q) --->
> x is the list (a q c)
>
> "Lists" in Mathematica may not be. e.g.
> f[n_]:=(Print[n];Hold[f[n]]);
> q=Table[f[i],{i,1,3}]
> q[2]= 2
> FAILS.
> ReleaseHold[q[2]] re-evaluates not just q[2], but every element in q.
>
> It prints 1,2,3
>
You seem to use the wrong notation here. You have to use [[ ]] (double
brackets),
not [ ] (single brackets). Otherwise instead of extracting a part of a
list, say,
you are trying to index into an indexed variable (hash-table).
Lists *are* mutable in Mathematica, when stored in a symbol. So, if you
assign
a = Range[10]
you can then modify some part in-place
a[[3]] = 100
but if you use
b[1] = Range[10]
then you can not use
b[1][[3]] = 100
Part assignments work not only for flat lists, but for any expressions
stored in a symbol.
>
>
> > Clearly Mathematica must store some
> > information in the head of every object to keep track of objects that
> > need reevaluation, and you wouldn't want each list node to be bloated
> > out in that way.
>
> It actually works the other way. If some element of a "List" is
> altered, then every element in that array must be re-evaluated. So it
> is a big disadvantage. See the example above, with q[2].
>
Again, this is not true. You weren't careful with the syntax and did not
test your example.
>
> The point I was making regarding "Lists" is that Wolfram is using a
> word for something quite different from the list data structure.
> This is one among a number of reasons to not use Mathematica for
> computer science.
>
I would probably agree for the first course in pure CS, for which Scheme
will
arguably be a better choice. But once the students get past the basics,
I agree with others that Mathematica can still teach a lot, if only for its
model of computation that is different, and its level of interactivity and
availability of many algorithms. And it can be an invaluable tool for
analysis
and development of algorithms, for the same reasons.
>
> Linked lists are used all the time in Mathematica. g[h[x]] is a linked
> list.
>
It will only be a linked list if you interpret it so, and if g and h are
inert heads.
In general, this is just a symbolic expression, and you will have to
provide a
context to it, to assign any semantics to it.
All in all, I don't say that I totally disagree with you - I actually agree
with many
of your points if I look from the pure CS viewpoint. But, as I already
said, this
may not be the only one, or even the most relevant one, in the context of
currently
dominant uses of Mathematica.
And this is not the first time I express this opinion in my reply to you :)
Regards,
Leonid
>
>
> By the way f[x] or Sin[x] looks sort of like a "function" but with
> square brackets. But it is not really. It has something to do with
> rules, patterns, evaluation, etc. As I recall, in SMP, Wolfram's prior
> CAS before Mathematica, such things were called Projections.
> This was probably too confusing, In any case the term was dropped.
> Maybe the people who knew other meanings for projection were able to
> get to him (e.g. graphics people?) in a way that computer scientists
> could not.
>
>
> http://www.stephenwolfram.com/publications/articles/computing/81-smp/1/text.html
>
>
> RJF
>
[toc] | [prev] | [next] | [standalone]
| From | Daniel Lichtblau <danl@wolfram.com> |
|---|---|
| Date | 2013-06-04 03:14 +0000 |
| Subject | Re: Interval vs default, was Re: Mathematica numerics and... Re: Applying |
| Message-ID | <kojm34$kbv$1@smc.vnet.net> |
| In reply to | #14471 |
I'm clipping quite a lot as this is already too long. Also some points were clarified, in both directions, off-line and I won't go into all of them. I'm not trying to respond to every point raised, just to a few that I think are compelling. And, alas, this is probably way too technical anyway. > There is a wikipedia entry on the topic that (at least as of this time > and date) is pretty good. The Wikipedia article in question is this. http://en.wikipedia.org/wiki/Significance_arithmetic In brief, I don't much like it. Little is said about how significance arithmetic really works (using first order approximations from Taylor series). And it seems to mix "significant figures arithmetic" with significance arithmetic. That is, to say the least, confusing. > The important quality of interval arithmetic that is not preserved is > that interval arithmetic (done correctly) preserves validity. That is, > the correct answer is guaranteed to be enclosed in the result. This is true but I think less important than one might think at first glance. It is certainly necessary for some purposes. e.g. mathematical proofs, to have error fully enclosed. It is less important for, say, reliable computation, provided one has determined that results are not corrupted, say by precision becoming too low for the first order model to hold up. I will give an example that more or less stradles these two worlds. See: http://ccsenet.org/journal/index.php/jmr/article/view/22480/14613 A counterexample is indicated to a conjecture from 2003. The code used to verify the counterexample invokes NSolve at 500 digits. If I recall correctly the exact computation would take longer than my patience allows, and finding an easier example that would be faster was likewise beyond my patience. I am confident that the counterexample holds up just fine. This despite the fact that one needs approximate arithmetic to see it through, and despite the fact that significance arithmetic is used to find and count real- valued solutions. Even the referee, who was in other respects quite skritchy, did not argue this point. (Had that happened, I would simply have convinced Mathematica to validate that or a different counterexample, and probably unsettled the referee even more in so doing.) > It seems to me that the default arithmetic is fairly complicated. Each > extended float number F has some other number E associated with it > (guess: it is a machine float representing something like log of > relative error), and calculations require mucking about with F and E > both, e.g. some calculations involving condition numbers relating to how > fast a function changes as the argument changes. Yes, that all comes from the chain rule and first derivatives. > I don't understand the derivative argument -- intervals can be computed > essentially by composition of interval functions. This may be overly > pessimistic compared to actually finding extrema, but it is, so far > as I know, fairly easy. Maybe I am missing something basic, but I don't think it is actually so easy. How do you determine the spread of an interval when evaluating some transcendental function? With trigs, on the real line, one can take advantage of periodicity, monotonicity between peaks and valleys, etc. But for arbitrary functions i would think one must work to either locate, or get outer bounds on, extremal values when evaluation on an interval. This does not strike me as either easy or computationally fast. > > A drawback, relative to interval arithmetic, is that as a first-order > > approximation, in terms of error propagation, significance arithmetic > > breaks down at low precision where higher-order terms can cause the > > estimates to be off. I will add that, at that point, intervals are going > > to give results that are also not terribly useful. > > An advocate of interval arithmetic (and at least for the moment I will > take this position :) ) would say that interval arithmetic guarantees > a valid answer. That is, the answer is inside the interval. Sometimes > the interval may be very wide, even infinitely wide. But it contains > the answer. Not so for significance arithmetic. While it may be > appropriately modest for the documentation for N[] to say that > N[expr,n] >>>attempts<<< to give a result ... This is not really > what interval arithmetic does. It guarantees... All fair points, though I do say a bit about reliability above. I will add to that here with a short description of the underlying mechanics. We have a bignum float and also a machine float to record and track precision of the bignum. While this is an implementation aspect, all the same it often makes sense to view a number as x + dx, where the 'dx' part indicates the error range. Error is tracked using derivatives to approximate. For example, Plis[] can be fully bounded in this first order model since (x+dx) + (y+dy) = (x+y) + (dx+dy) Well and good. What about Times? (x+dx) * (y+dy) = (x*y) + (x*dy + y*dx) + (dx*dy) The error terms tracked are the middle two-- the dx*dy is in effect dropped. So how bad is this error dropping? Consider how we actually represent our error. We use a machine double, and that itself has a certain granularity. A bit of thought, which I will not attempt to write out here, will show the following: for multiplication, the second order error that is discarded will be less than the granularity of error that can be recorded, provided the precision remains higher than that can be kept in a machine double. For all systems on which Mathematica runs, this amounts to around 16 digits. Another way to view it is this. Were we to add one ULP to our precision loss (we do not do this, ity's just hypothetical), we would fully bound error from Times provided precision is above the granularity implied by this ULP. (Paradoxically this means that using e.g. quad precision for error would require greater precision for certainty of enclosing this error. But on the flip side precision degradation would be far slower. Similar happens for e.g. inverting (as in 1/(x+dx) and taking of integer powers. While these are by no means the only operations one does, they are the most common in many algorithms at least of the sort I run across. There are a few more things I might be able to say but I think this one response has already taken me a bit afield. Maybe another post. Daniel Lichtblau Wolfram Research
[toc] | [prev] | [standalone]
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | comp.soft-sys.math.mathematica
csiph-web