Wikipedia:Reference desk/Archives/Computing/2019 February 19

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 19

Annoying iPhone banner

When I double tap the home button on my iPhone, it displays all the tabs I have open. But it often also brings up a small banner at the bottom of the screen, usually for the podcast app, telling me 'Good Morning' and suggesting I use the app. I find this annoying. Is there any way I can turn off this function? I have an iPhone 5s, iOS 12.1.4

Try going to Settings > General > Spotlight Search and turning off "Siri Suggestions". --Canley (talk) 11:22, 19 February 2019 (UTC)

Description for OML (Q11794389)

Hello all,

I would like to add a description to the Wikidata object OML (Q11794389). The linked polish Wikipedia article pl:OML says something like "language used when creating bindings to an external programming" which is not really clear to me. In addition, Object Manipulation Language is already an alias. Not sure if the definition "programming language" fits here. Any recommendations? Many thanks in advance. Best regards --Hundsrose (talk) 07:16, 19 February 2019 (UTC)

Hi, Hundsrose. Your translation lacks one word – it should read "language used when creating bindings to an external programming language". Alas, even though Polish is my language, I don't understand that, either. I have asked the creator of the plwiki's stub to expand it a bit (pl:User talk:Durski#OML), but got no reply yet. --CiaPan (talk) 15:56, 19 February 2019 (UTC)

@CiaPan: Thank you so much for your answer and your action. Very kind of you. --Hundsrose (talk) 17:06, 19 February 2019 (UTC)

Solve cubic equations

In one of my programs I need to solve a large number of cubic equations with integer coefficients. I'm only interested in positive real solutions. I have code for the analytic solution of cubit equations, but it executes too slowly. Right now I'm trying Newton's method, but a significant amount of the time it gets into a loop alternating between two values (I think that means that there are no real roots).

When I took numerical analysis about 40 years ago, I remember that one of the first things we did was a very simple, non-iterative method to get roots of polynomials. (Has rational roots if integer coefficients.) I can't remember the method or its name, and I haven't been able to find it in searches and reading articles.

Can someone point me to that method (or perhaps a better one)? Bubba73 ^{You talkin' to me?} 08:34, 19 February 2019 (UTC)

A cubic equation with integer coefficients must always have at least one real root. The ones that don't converge are probably because the initial value you are feeding in is in a region of the curve that does not monotonically lead to the root, or else you are closing on a point of inflection. The way to proceed is to first find the two extrema (which involves solving a quadratic only). If the function at one extremum has a positive value and the other negative, then there are three real roots, otherwise there is only one. If there are three roots, one is above the higher (x-value) extremum, one below the lower, and one between the two. If there is only one, the sign of the function at the the extrema and the sign of the cubic term tells you which "end" of the function the root is at. Alternative methods for finding a root at root-finding algorithm of which the conceptually most simple is probably the bracketing method. SpinningSpark 13:19, 19 February 2019 (UTC)

@Bubba73: I'm not quite sure what kind of problem you describe. But, if it is lots of independent cubic equations, each with a single variable, isn't Cubic function#Algebraic solution appropriate? --CiaPan (talk) 13:39, 19 February 2019 (UTC)

Isn't that what he's tried already? That is the analytic solution. Although, I agree, it's hard to believe that anything else is going to be any faster. SpinningSpark 13:59, 19 February 2019 (UTC)

@User:Spinningspark I really doubt it. The algebraic solution is IMHO the fastest possible way (provided we're talking about separate, independent equations with one variable each, as I clearly assumed above). Iterative methods like Newton are slower and can be divergent. If the 'analytic' method 'executes too slowly', as Bubba73 said, so that OP chose to switch from the 'analytic' method to Newton's, their 'analytic' method must have not been the algebraic one. --CiaPan (talk) 15:30, 19 February 2019 (UTC)

I have my old code for the exact solution, but it uses a lot of trig functions, so wouldn't be very fast. However, they are depressed cubic equations (no $x^{2}$ term, so the link to cubic equation should work fine, thanks for that. And yes, you are right about the iteration bouncing between two values - it is where there is a valley in the real function that doesn't cross the x-axis, related to a complex root. Bubba73 ^{You talkin' to me?} 16:27, 19 February 2019 (UTC)

The code for solving a cubic equation I have is based on "Numerical Recipes" by Press, Flannery, Teukolsky and Vetterling. I takes several roots and four trig functions, beside a lot of arithmetic. But it is designed to avoid trouble with round-off errors. It does about 10,000,000/sec on my computer, and I need to do trillions of them. Bubba73 ^{You talkin' to me?} 19:39, 19 February 2019 (UTC)

Well, as I've implemented them, Cardano's method is only about 25% faster. The time-consuming part is taking the cube root using log and exponential. Is there a faster way for cube root? Bubba73 ^{You talkin' to me?} 20:17, 19 February 2019 (UTC)

@Bubba73: As far as I know there exist some approximations for elementary functions with polynomial and rational functions, alas I do not know them... Please see the page about the cube root — the Cube root#Numerical methods section contains quite fast iterative method for approximating the function. I'm not a mathematician and have not used mathematics at this level for a long time, but hopefully Halley's method page will let you derive a necessary approximation of the iterations' convergence. May be it will turn out faster than exp(log()) ...? --CiaPan (talk) 21:25, 19 February 2019 (UTC)

I thought of what is probably a better approach. Since I am looking only for positive integer solutions, and the last step is the cube root, I can tabulate the cubes of integers and search on that table rather than doing the cube root calculation. That should be a lot faster, but I haven't tested it yet. Bubba73 ^{You talkin' to me?} 03:01, 20 February 2019 (UTC)

Rational root theorem is the one I was thinking of but couldn't remember. Bubba73 ^{You talkin' to me?} 06:39, 20 February 2019 (UTC)

I think more than algorithms you have to ask about constant factors here, and note that if you really are going to be solving these cubics on a massive scale ("trillions" by itself isn't much) you probably want to use a GPU. So asking yourself how you can parallelize the algorithm can be important in algorithm selection. The algebraic solutions IIRC involve classifying the equations into different branches which might get in the way of a SIMD solution. Also, decide how much accuracy you need: a lookup table might beat a numerical root finder if you don't need much. If you have AVX-512 hardware, look at the Intel SPMD compiler: https://ispc.github.io/ . Again though, the next thing after that is probably a GPU. I also wonder if a second-order Newtons' method would be faster than the usual first-order one in this specific case. It might depend on whether you have some info about the equations that lets you pick a good initial guess. 173.228.123.166 (talk) 21:34, 20 February 2019 (UTC)

I was planning to parallel the calculations, but I don't know about the GPU and other hardware. But I'm looking for integer solutions, so I don't know how appropriate that would be, I'll just stick to integer arithmetic. I think I can get it to take only a few days to execute in parallel on an i7 or Xeon. Bubba73 ^{You talkin' to me?} 21:46, 20 February 2019 (UTC)

You can do integer calculations on AVX or GPUs. Also, meant to mention another reason to beware of algebra: computer division and exponentiation (cube roots, nth roots, trig etc.) are much slower than multiplication or addition (square roots are about the same as division). So it's faster to do a calculation with several multiplications than a cube root. Integer solutions sound like low precision so maybe a rough numerical method can suffice. AVX and GPU programming with OpenCL or Cuda look like C or C++ with a few changes to facilitate vector processing. Whether it's worth it again depends on just how much of this calculation you want to do. Yeah if it's a one-time thing that you can do in a few days on an i7, then that's probably easiest. 173.228.123.166 (talk) 23:21, 20 February 2019 (UTC)

I don't know how to use AVX or GPU. These aren't exactly low-precision integers - they will be 64-bit integers and on a similar problem I did limited multiprecision integers. I might need to do that again. (Integers have to be exact.) Bubba73 ^{You talkin' to me?} 06:32, 21 February 2019 (UTC)

AVX can handle int64, not sure about current gpus. Programming them isn't that much different from ordinary C programming but there is still some ramp up, new tooling to get used to, etc. It's not worth it if you can finish in a few days without it. It's probably worth looking into if you have years worth of these calculations to do. 173.228.123.166 (talk) 10:02, 21 February 2019 (UTC)