Tag Info

Hot answers tagged

26

Fibonacci numbers grow approximately exponentially. The 1,000,000th Fibonacci number is huge, it has 208,988 decimal digits. It also takes a fair amount of memory to store: ByteCount@Fibonacci[1000000] (* 86856 *) This is 86 kB. Does Mathematica store huge numbers efficiently? How many bits/bytes do we need at minimum for this number? Let's calculate ...


23

Update 20/02/2015 I've now adapted my code to work with a binomial distribution, since that seemed to be the most problematic case for the OP. The relevant C++ code is at the bottom of this answer. Needs["CCompilerDriver`"] BinomialVariateLib = CreateLibrary[{ToString[NotebookDirectory[]] <> "binomialvariate.cpp"}, "BinomialVariateLib", ...


22

The general case There are indeed some functions in Mathematica that are/were not performing nicely. The one I am most scared of is Total (the issue is addressed here) (update: apparently Total has been fixed in version 10.0.2). Pickett provides some more examples in his comment. But I feel the case of Union is different, as it is simply specialised for a ...


22

I can't take much credit for this answer--I hadn't even got version 10.2 installed until J. M. commented to me that these functions could be written efficiently in terms of the Hamming weight function. But, it is understandable that he doesn't want to write an answer using a smartphone. The definition of the built-in ThueMorse is: ThueMorse[n_Integer] := ...


22

First off, your function is very simple without any hard number-crunching, so it will always be hard to get a large speedup for the compiled version. Secondly, your Parallelization option for Compile is useless because it doesn't do any parallelization this way. Let me give slightly changed versions of your examples and explain how you can achieve a large ...


21

I've decided to expand on my comment. Before I delve into the solution, let's all pause for a moment and marvel at the stereographic parametrization of a unit circle: $$\begin{pmatrix}\frac{1-t^2}{1+t^2}\\\frac{2t}{1+t^2}\end{pmatrix}$$ Sometimes also referred to as the Weierstrass substitution, it has often been used as a tool in the solution of algebraic ...


21

Chunks of weak compositions Here is slightly modified version of algorithm used in Combinatorica`NextComposition converted to a LibraryFunction. Needs["CCompilerDriver`"] " #include \"WolframLibrary.h\" DLLEXPORT mint WolframLibrary_getVersion() { return WolframLibraryVersion; } DLLEXPORT int WolframLibrary_initialize(WolframLibraryData libData) { ...


20

This is a poor use of the random functions in Mathematica. As clearly stated in the documentation, generation of variates one at a time has significant overhead, and generating them en masse has significant benefits, particularly with statistical distributions: For statistical distributions, the speed advantage of generating many numbers at once can be ...


20

My answer is based on a modification of a binary heap. Basically the construction looks something like this. We start with a binary tree: Notice that if we label the nodes breadth-first, the labels have an interesting property. Each parent node $n$ has two children, $2n$ and $2n+1$. This also works in reverse: the parent of node $n$ is node ...


19

You can just step through $i$ and $j$ while trying to simultaneously satisfy: $$i^2+(i+1)^2=j^2+(j+1)^2+(j+2)^2$$ Just loop and if the inequality is too small on the left, increment $i$. If it's too small on the right, increment $j$. That looks like this: Clear[f, g, i, j]; f[i_] = i^2 + (i + 1)^2; g[j_] = j^2 + (j + 1)^2 + (j + 2)^2; max = 10^6; i = 1; j ...


18

Following the advice in comments, I've made a test library for BesselJ[1, #] & function to evaluate via GSL. I still consider it a workaround, so if you find a way to use Mathematica built-in functions with good performance, please do make a new answer. Needs["CCompilerDriver`"] besselJ1src = " #include \"WolframLibrary.h\" DLLEXPORT mint ...


18

We can take advantage of the fact that IntegerDigits is very fast when the base is large. But not too large: no bigger than $2^{63}-1$ on a 64-bit system or $2^{31}-1$ on a 32-bit one, because Mathematica's machine integers are signed. Additionally, non-power-of-two bases require more work to get the result than just partitioning a bit-string, and are ...


17

It seems that there is a significant overhead every time a color scheme is switched. Once a scheme is loaded each use is fast, but changing color schemes apparently unloads and reloads the mechanism. The result is that the speed of application is directly related to the frequency of switching. With sorted values there is only one switch and application is ...


17

Preface Below, you will find two different solutions. For understanding the problem itself, the first, iterative solution is better suited since it gives insight in how the solution can be found without directly executing the instructions given as input. Iterative Solution Detailed explanation To explain the idea behind this approach let us work with a ...


17

Here is a summary of comments (before @ciao's best answer above), with a change in notation. These functions calculate the number of partitions of n into exactly k distinct parts of size at most m. NumberOfWays000[n_, k_, m_] := Count[Map[Length,Map[DeleteDuplicates, IntegerPartitions[n,{k},Range[m]]]], k] NumberOfWays001[n_, k_, m_] := ...


16

You´ll find a lot of Mathematica Code on the internet regarding this problem. Your code generates the collate sequence for every number without taking into account, that there are a lot of duplicate calculations. You can approach it via collatz[n_] := collatz[n] = If[EvenQ[n], n/2, 3*n + 1] to remember the calculations, then... collatzSequence[n_] := ...


16

Unless both lists given to Equal are packed arrays Equal will first unpack. Unfortunately for this case {} is not a packable expression, therefore list == {} will always unpack list, assuming it starts packed. That unpacking takes time: test = RandomInteger[100000000, 10000000]; Developer`FromPackedArray[test]; // AbsoluteTiming {0.207012, Null} ...


16

This happens because of unpacking when the numbers exceed $MaxMachineNumber: fast = Dot @@@ Partition[tab, Divisors[3960][[42]]]; Developer`PackedArrayQ /@ fast (* {True, True, True, True, True, True, True, True} *) Max[fast] <= $MaxMachineNumber (* True *) slow = Dot @@@ Partition[tab, Divisors[3960][[43]]]; Developer`PackedArrayQ /@ slow (* {False, ...


16

Here's an edited version of my answer to a related question (elsewhere). Since your central question was about speed (or time complexity), you might wish to know an important result from elementary theory of algorithms and computational complexity, which is that the time and space complexity of matrix multiplication depends upon the order of such ...


16

This seems pretty quick, particularly on larger cases / larger k, e.g. 451, 29, 101 finishes in a few seconds on the loungebook. N.B. - I have not tested this exhaustively, just thrown together from ideas... If[Min[#3, #1 - Tr@Range@(#2 - 1)] < 0, 0, SeriesCoefficient[QPochhammer[-x y, x, Min[#3, #1 - Tr@Range@(#2 - 1)]], {x , ...


15

Okay, this is a bit of an embarassment. Here is a very small modification of the original code. I simply made explicit option settings, made a denominator to Sin explicitly real, that kind of thing. My tests show the same timing as the original, give or take an iota. ie = 200; ez = ConstantArray[0., {ie + 1}]; hy = ConstantArray[0., {ie}]; fdtd1d = ...


15

A fast uncompiled alternative without pattern matching is to use the NonzeroPositions property of SparseArray, as long as you're dealing with numerical data. list = RandomInteger[{1, 100}, 10^7]; Needs["GeneralUtilities`"] SparseArray[Unitize[list - Max[list]] - 1]["NonzeroPositions"] // AccurateTiming (* 0.120459 *) Position[list, Max[list]] // ...


15

You can speed it up by only invoking the NearestFunction once: KPosition3[x_, y_] := Module[{step0, step1, nf}, step0 = Thread[x -> Range[1, Length@x, 1]]; nf = Nearest[step0]; step1 = nf[#, y] & /@ x]; Running your three timing tests gives: {0.003057, 0.004344, 0.051009}


15

Here is a totally different approach based on the fact that successive products forming the generating function are due to multiplication by a binomial $1+t*z^j$. Form a matrix $v$ of zeros with $n+1$ rows and $k+1$ columns. Initialize the top left corner to 1. Iterate $v=v+w$ where $w$ is the matrix $v$ shifted down by $j$ rows and to the right by 1. The ...


14

Your test is quite synthetic: you take only few first elements. If you you have longer sequence of positive elements then build-in LengthWhile is faster lst = RandomInteger[{-1, 30000}, 100000]; rst1 = LengthWhile[lst, # >= 0 &]; // AbsoluteTiming rst2 = lengthwhile[lst, # >= 0 &]; // AbsoluteTiming rst1 == rst2 (* {0.096340, Null} *) (* ...


14

There are several reasons. Firstly the built-in function has some minor overhead to check the arguments and call the appropriate internal function depending on whether the first argument is a list, a sparse array or an association. Secondly, with a packed array, LengthWhile uses compilation in an attempt to increase performance. There is some overhead in ...


14

You miss that many Mathematica functions are listable. It allows you to write a fast and clear code init2[distance_] := uniMass Total[liuQuartic[distance, h] UnitStep[2 h - distance], {2}] h = 0.1; uniMass = 1.0; liuQuartic[d_, h_] := d^2 - h^2; totalPos = RandomReal[1, {1119, 2}]; res1 = initializeDensity@computeDistance[totalPos]; // AbsoluteTiming res2 ...


14

idtz = Internal`DeleteTrailingZeros; trim0a = With[{t = Reverse/@ idtz/@DeleteCases[#, ConstantArray[0, Length@#[[1]]]]}, Reverse /@ idtz /@ t] &; trim0b = With[{t = DeleteCases[#, ConstantArray[0, Length@#[[1]]]]}, Fold[idtz@#2@# &, #, {Reverse, Reverse}] & /@ t] &; Equal @@ (#@test & /@ {trim0, trim0a, ...


14

For a 1D list you can also use Pick[Range@Length@list, list, Max@list]


13

Update: the lhs of $i^2+(i+1)^2=j^2+(j+1)^2+(j+2)^2$ is always odd so $j$ should be even. The fastest solution I found: max = 10^12; {(Sqrt[3 + 6 (# + 1)^2] - 1)/2, #, #^2 + (# + 1)^2 + (# + 2)^2} & @@@ (2 Position[#, 0]) &@UnitStep[Abs[# - Round[#]] - 1.*^-10] &[ Sqrt[0.75 + 1.5 #^2] - 0.5] &@ Range[3., Sqrt[max/3.], 2] // ...



Only top voted, non community-wiki answers of a minimum length are eligible