fdej

Check out the Wikipedia article https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number for some examples:

ARIA uses 1/π (indeed, why not pi?)

MD5 uses sin(n) (why not cos(n) or sqrt(n)?)

SHA-1 and SHA-2 use square roots and cube roots of small primes (why not sin(n) or pi?)

DFC uses e.

NewDES uses the United States Declaration of Independence.

RC5 uses both e and the golden ratio.

BLAKE uses "a table of 16 constant words which are the leading 512 or 1024 bits of the fractional part of π". (Here you see how things like bit or byte order can give you more choices.)

If primes derived from pi are not suspect, then that surely goes for primes derived from 1/pi, e, sqrt(2)... as well? What about bit order, byte order?

The problem is that there are lots of small choices involved in picking "nothing up my sleeve" numbers and deriving data from them. Each small choice may seem trivial in isolation, but taken together, the parameter space is so large that you can derive virtually anything from "nothing up my sleeve" numbers.

Bernstein et al. made a point of exactly this in the paper https://bada55.cr.yp.to/bada55-20140722.pdf by deriving the string "BADA55" from "nothing up my sleeve" numbers.

Very large or small numbers are useful in combinatorics and number theory. It can also happen that they are needed for intermediate steps in an algorithm, even when the inputs and outputs are moderate (the same reason that 15 digits sometimes isn't enough even when you just want 3 digits of output). Granted, you can generally work around exponent range limitations using tricks (scaling values properly or introducing logarithms), but that can obviously be a hassle.

Sure, but:

1) As soon as you wrap it in a Python class, much of that speed advantage goes away.

2) Double-double doesn't solve the problem with the limited exponent range of doubles.

3) When the goal is to allow setting the precision to any number of bits you like, having a separate implementation for X bits complicates things a lot, especially when the X-bit arithmetic doesn't quite behave like Y-bit arithmetic for X != Y (double-double behaves somewhat differently from 108-bit floating-point).

IMO, double-double would be most interesting as a NumPy extension.

It was warmed up.

Sadly, PyPy doesn't speed up mpmath a whole lot.

Edit: I just tested multiplying two 100 by 100 matrices, and got a 5x speedup with PyPy compared to CPython. Which is nice but not amazing.

Author of mpmath here. It depends a lot on what you're doing.

A single floating-point arithmetic operation in mpmath at low precision involves something like 100 "Python cycles" (bytecode ops), each of which takes perhaps 100 machine cycles.

That makes it, roughly:

100 times slower than machine arithmetic in Python.

10000 times slower than machine arithmetic in C (or NumPy if you can vectorize your code fully).

100 times slower than arbitrary precision floating-point arithmetic implemented in C (~100 machine cycles).

These are obviously just order of magnitude estimates.

However, low precision is the worst case, relatively speaking. mpmath uses Python longs internally, and it can also use GMPY when available. At sufficiently high precision, the time is dominated the Python/GMP kernel for multiplying integers and performance is close to other bignum implementations.

Also, for computing transcendental functions, mpmath uses fixed-point arithmetic internally, which reduces overhead a lot.

The biggest problem with mpmath is that it doesn't implement algorithms that scale optimally for all operations, and a lot of the error analysis is completely nonrigorous.

Since 2012, I have been developing a C library (https://github.com/fredrik-johansson/arb/) that solves many of the shortcomings of mpmath. It is obviously much faster at low precision (the factor 100 mentioned above), it generally uses much better algorithms, and it tracks error bounds automatically using interval arithmetic.

Publishing in the most prestigious journals is hugely important. The first thing many academic hiring/promotion/grant committees look at is how many Nobel Prizes you've won, the second thing is how many publications you have in Nature or Science. Everything else is just for breaking ties. I've even heard that there are fields where having any conference publications counts against you.

PhD in symbolic computation (RISC). Symbolic integration is not my field of research, though, and I don't really know anything beyond the basics (covered in courses on computer algebra). Passively attended plenty of seminars and conference talks on symbolic integration, though, and for a couple of years, I did share office with Clemens Raab who is one of the experts on the Risch algorithm.

There is no complete implementation of the Risch algorithm. None of the implementations fully implement the algebraic case. Besides, the Risch algorithm doesn't solve all symbolic integration problems in practice:

* Even when it succeeds, it doesn't necessarily give you the simplest possible form of the solution.

* It is concerned with elementary functions, but real-world problem often involve non-elementary functions (like Bessel and hypergeometric functions). You can extend the Risch algorithm to work with such functions, but this is complicated.

* It doesn't allow computing parametric answers for common parametric families of integrals (this needs to be done using heuristics and lookup tables).

* It doesn't give you an algorithm for definite integration, except in simple cases. Even with proper definite integrals, you need to be extremely careful with branch cuts when applying the fundamental theorem of calculus. For improper definite integrals, systems like Mathematica generally try to go via convolutions of Meijer G-functions, using huge lookup tables and simplification heuristics.

* Even more fundamentally, the Risch algorithm (and symbolic integration more generally) puts heavy demands on the underlying symbolic computation engine. In particular, it depends on the ability to decide whether an expression is equivalent to zero, which in fact is an undecidable problem, and this strictly speaking makes the Risch "algorithm" a non-algorithm (though it is a proper algorithm when restricted to a ground field where zero testing is effective, such as Q).

2^34240923842043983204982-1 is divisible by 3.

Because GMP is designed for arbitrary size integers, and for safety. Given two mpz_t operands to multiply, it needs, in some order, to:

* Dereference pointers

* Extract the signs of both input operands

* Extract the sizes (number of limbs) of both input operands

* Check whether the output variable has enough space for the result, and otherwise, reallocate it

* Check whether the output operand is the same object in memory as either input, and in that case allocate temporary scratch space and make a copy of the data (since the multiplication algorithm doesn't allow aliasing)

* Decide which multiplication algorithm to use (different algorithms are optimal for different sizes)

* Call the chosen multiplication algorithm

* In the multiplication algorithm, loop over the variable numbers of limbs

* Actually perform the arithmetic operations in the multiplication

* Normalize the resulting size by checking whether the top limb of the output is nonzero

* Write the sign and size of the result to the output variable

In addition, mpz_t variables need to malloc and free every time they are created and destroyed. This is not so much a concern in practice, because optimizing programmers will reuse variables as much as possible. (However, some language wrappers don't reuse GMP variables, and are unnecessarily slow as a result.)

You can use GMP's internal functions if you want faster arithmetic and either know that overflow cannot occur or want to do overflow checking manually. For example, if z, x and y are pairs of 64-bit integers, not aliased with each other, then mpn_mullo_basecase(&z, &x, &y, 2) does a 128-bit multiplication (mod 2^128). Depending on the platform, using mpn_mul_basecase to compute the full product with some scratch space might be faster.

This kind of code should generally be faster than calling the general and safe function mpz_mul, though it will still have a few cycles of overhead for the function call and looping.

For integers up to a few hundred bits, inlined fixed-size code is always going to be faster.

Why does it need to be updated? Valgrind is that rare piece of software that always has been working absolutely flawlessly for me.

The scanned area is still just 1/1000 of the Indian Ocean, and very far from the coast. Finding two ships doesn't sound so bad to me.

A stackexchange site with an automatically posted "question" for each arxiv submission would be an interesting idea.

This is less of a problem when you consider that peripheral functions tend to have verbose, descriptive names. Is GeoProjection really fundamentally worse than Geo.Projection? The upper case convention by itself greatly reduces the chance of collisions with user-defined functions and variables.

Nice project. I wonder, would https://commons.wikimedia.org/wiki/Category:Caricatures_by_L... appear as funny to a blind person as they are to a seeing person?

It seems to me that all we really need is a way to attach reviews/endorsements to papers already posted on the arxiv. Tim Gowers's initiative is a good start, but with just one specific overlay journal, a tiny one.

Thanks for the correction! I just came across tested.com a few months ago, and probably wouldn't have found it without the 'big names'.

I loved MythBusters early on, but I haven't been able to stand watching the show for several years, save for the occasional episode. You know the drill: the heavy editing, the grating narrator, the scripted conversations, the sponsored "myths", the filler explosions.

The fun for me was always in seeing Adam and Jamie doing the actual research and building in order to test a myth. I liked being able to follow their thinking process. They would sometimes run into dead ends before even getting to the building stage, forcing them to rethink their approach. That gives a better picture of what science and engineering really is like, too. I suppose there's always been some scripting and editing, and the early seasons were flawed in other ways, but it definitely seemed to be a lot more genuine early on.

It's not about an entertainment tradeoff for me, as I simply don't find the current show format entertaining. But then, I guess I'm just not in the show's target audience anymore. I can accept that. Some good news, though, is that Adam and Jamie have started a website [1] where they (primarily Adam) show off builds and gadgets, without the shackles of the TV show format. For example, [2] is a video in which Adam Savage explains a tool stand for 14 minutes, which I honestly found more entertaining and interesting than any MythBusters episode I can remember seeing recently. I like seeing the nuts and bolts of their builds and experiments, quite literally.

I hope the final season ends on a high note. All things considered, it's been a good run, and the team behind MythBusters deserve a huge amount of credit for what they've done.

[1] http://www.tested.com/ [2] http://www.youtube.com/watch?v=TWQAYfGxsPE

Some of us need would need to run for an hour just to get away from the city blocks. Well, I'm currently fortunate enough to have a park just nearby, though it's a rather small and boring park... nothing like living next door to a vast forest full of trails (as I did when growing up).

Sage doesn't really use SymPy a whole lot. Most of the core algebra in Sage is based on C libraries like MPIR, Flint, Singular, Pari...

Nemo uses some of the same libraries under the hood, but there's much less overhead. This is in part due to Julia being faster than Python (although Sage works around that to some extent by using Cython), and in part due to Nemo using tighter algorithms/code.

Note that Nemo is currently more geared towards purely algebraic computation, though. It doesn't currently have S-expressions with support for symbolic integration and the like (Sage mostly uses Pynac and Maxima for this).

Not necessarily the most representative benchmark, but:

    >>> from sympy import *
    >>> from time import clock
    >>> var('x y z t')
    (x, y, z, t)
    >>> f = poly(1 + x + y + z + t)
    >>> p = f ** 20
    >>> t1=clock(); q=p*(p+1); clock()-t1
    53.828634

    julia> using Nemo
    julia> Rx,x=PolynomialRing(ZZ,"x");
    julia> Ry,y=PolynomialRing(Rx,"y");
    julia> Rz,z=PolynomialRing(Ry,"z");
    julia> Rt,t=PolynomialRing(Rz,"t");
    julia> p = (1+x+y+z+t)^20;
    julia> @time p*(p+1);
    1.593379 seconds (129.24 k allocations: 6.758 MB, 0.82% gc time)

Edit: oops, I forgot a variable which made the benchmark totally unfair!

My impression living in France for the last year is very similar to yours. It's the mecca of paperwork (but doing taxes was relatively easy).

And if you're required to supply some documentation from another country, you're likely to be required to get it translated to French by an official translator (which not only takes time but can be quite expensive). In contrast, I've never had a problem handing in German documents to authorities in Sweden and Swedish documents to authorities in Austria. Documents in English have certainly been accepted everywhere outside of France.

The catch-22s are the best. Renting an apartment requires that you have a French bank account, and getting a French bank account requires that you already have somewhere to live in France...

This is not quite correct. A finite ring can only have finitely many primitive roots of unity, so the length of the FFTs you can compute in a ring of fixed size is bounded. To compute arbitrarily long convolutions over a finite ring, you need to extend the ring with more roots of unity (for example, using the Schönhage-Strassen trick), and this increases the complexity.

Indeed, having a fast way to multiply in Z[x] gives you a fast way to multiply in Z and vice versa. In the reverse direction, you can encode the polynomial f = 2x^2 + 6x + 3 as 30602, and 30602^2 = 936482404 tells you that f^2 = 4x^4 + 24x^3 + 48x^2 + 36x + 9 (of course, on a computer you do this in binary as opposed to decimal).

This correspondence is often exploited in both directions. If you ask a sufficiently sophisticated computer algebra system (SageMath, for example) to multiply two large polynomials with integer or rational coefficients, chances are that it will reduce the problem to multiplying two large integers, then reduce that problem to multiplying two large polynomials (but different from the ones you started with), and then proceed using recursive polynomial and integer multiplications to compute that product... (i.e. going through a sequence of transformations Z[x] -> Z -> Z[x] -> ...)

I guess we'll be removing cruft from the web.

110000 BOE per day = 7.78 GW. An estimate from 2013 cited on Wikipedia claims the cost of the vessel is US$10.8 to 12.6 billion. Is there a reliable estimate of how much solar power you could install for the same cost?

Basically everything that can be done with 80-bit floats can be done with techniques such as compensated summation and double-double arithmetic. This requires several 64-bit operations per operation, but those operations can take advantage of SIMD capabilities when processing several inputs in parallel.

The Doom engine uses a lot of global mutable state. In context, there's nothing wrong with this. Why pass around state explicitly when there's just one instance of the state? Multithreading wasn't on the horizon for game engines in 1993. Single CPU cycles were very much a concern. Developer time was also limited (most of this code was written by a single person in about a year). This wasn't a toy project that could have evolved in a million different ways, and it wasn't a crypto library either. There was a game that had to be shipped, and John Carmack was surely more concerned about getting the game engine to do precisely what it needed to do to run the game than proofing the code for hypothetical future scenarios.