algorithmjuliamathematical-optimization# Julia PLSQ - Integer Relationship Algorithm - anyone used it in anger?

I'm trying to use one of LLL or PLSQ integer relationship algorithms to obtain a truly optimal solution to the problem of finding fixed length mantissa coefficients for Remez approximating polynomials. It is proving rather tricky to do. I have successfully downloaded and installed the Julia PLSQ library code from Github and I can run its self tests OK.

However, I am not much further forward. I cannot see how to frame my question for solution or even use the PLSQ library on simple toy problems by looking at the sample code or reading the various original papers on this method. It is on the edge of advanced number theory and some of it looks like magick to me.

In simple terms what this algorithm does is when given a set of high precision real numbers a,b,c,d... it attempts to find a set of exact integers A,B,C,D with the smallest magnitude such that with chosen integers non-zero.

0 = a.A + b.B + c.C + d.D + ...

The aim is to round the hard won Remez polynomial coefficients to something that will fit in an IEEE754 mantissa whilst preserving the ratios between a,b,c,d,e as accurately as possible. Reports from Intel claim that it is superior to simulated annealing for this purpose. I do not have access to their code (unless SKS offers it).

I know what I want to do but actually programming it is proving very difficult. I'd like to see a couple of examples of PLSQ doing something that I can actually understand. Does anyone have any experience of using this esoteric package in anger?

I have read the "Gentle introduction to PLSQ" but found it almost as hard going as the original academic paper that announced the algorithm. I got to Exercise 5 before my mathematical intuition ran out. Thanks for any advice or pointers to an even easier introduction with simpler examples. I think I need PLSQ for Dummies. Sorry no MRE - I'm stuck!

I'm also struggling a bit with good search terms since hits for Oracle PL/SQL swamp my search engine results by 100:1.

Solution

I downloaded Pslq.jl from https://github.com/ikirill/Pslq.jl/blob/master/Pslq.jl

I then used the following code to solve exercise 5. Although I cannot figure out what is meant by identifying α:

```
include("./Pslq.jl")
α = 3.6502815398728847452
values = convert(Vector{BigFloat}, [α^i for i in 0:10])
result = Pslq.pslq_simple(values)
println(result.relation)
```

Output:

```
BigInt[-1449, 36, 2290, -20, -181, -52, -43, 4, -10, 0, 1]
```

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?