Comments (11)
Why don't you just find separate minimax interpolating polynomials for each interval?
from lolremez.
I want to approximate a polynomial for sign function in [-1,1]. My usecase is that I have an encrypted input x \in [-1,1] but I can't know if x is negative or positive. I am using "fully homomorphic encryption" which supports evaluating polynomials on encrypted data.
from lolremez.
That’s a very interesting use case! I’ll have a look at what can be done.
from lolremez.
Thanks a lot!
actually this problem is solved in the state of the art by what is called "multi-interval Remez algorithm", which computes Remez on [-1,-eps], [eps, 1]:
https://eprint.iacr.org/2020/834.pdf
from lolremez.
So, this specific case is actually a lot less complex than the general case, because you can use the technique for odd functions explained in the lolremez manual, the function you want to approximate is simply
For instance:
$ lolremez -d 5 -r 0.1:1 '1/sqrt(x)' '1/sqrt(x)'
double f(double x)
{
double u = -27.674387189032068;
u = u * x + 89.61852558307946;
u = u * x + -113.12718846240877;
u = u * x + 70.763443739725503;
u = u * x + -23.464237705608777;
return u * x + 4.8738244889926898;
}
$
Replacing
from lolremez.
Thank you!
do you have an idea on how to solve the general case?
from lolremez.
Or more specifically, is it possible to compute an approximation of a stepwise function? For example, approximating the following function:
f(x) = {-3 if x < -1, 0 if -1 < x < 1, 2 if 1 < x < 3}
In the domains: [-3+eps, -1-eps]
, [-1+eps, 1-eps],
[1+eps, 3-eps]`.
One way to do this would be to express f(x)
as the sum of two stepwise functions that have two branches, and then using your solution to approximate a stepwise function with two branches. However, I wonder if there is a way to compute an approximation of f(x)
using Remez directly.
from lolremez.
The Remez algorithm doesn’t work well with non-continuous functions. I would recommend helping it by making the functions continuous, or even smooth (C-infinity). You can for instance build a good such function using tanh()
. In your case:
The greater
Using the Remez algorithm on
However there is clearly a problem with LolRemez and that kind of function; most of the time it fails to converge and find a solution. I am going to investigate.
from lolremez.
Great, thanks!
from lolremez.
So, this specific case is actually a lot less complex than the general case, because you can use the technique for odd functions explained in the lolremez manual, the function you want to approximate is simply f(x)=1 and the range is [0.01,1].
For instance:
$ lolremez -d 5 -r 0.1:1 '1/sqrt(x)' '1/sqrt(x)' double f(double x) { double u = -27.674387189032068; u = u * x + 89.61852558307946; u = u * x + -113.12718846240877; u = u * x + 70.763443739725503; u = u * x + -23.464237705608777; return u * x + 4.8738244889926898; } $
Replacing x with x2 and multiplying the final result by x:
"How to approximate only use 7th-order polynomial?"
from lolremez.
Funny that I also saw this in search of a remez-like algorithm for FHE. Note that a Go implementation of the multi-interval method exists in Lattigo: https://github.com/tuneinsight/lattigo/blob/0d754047425ff9513bf6fbea717415a754911408/he/hefloat/minimax_composite_polynomial.go#L125
from lolremez.
Related Issues (20)
- Marvellous. A couple of small suggestions? HOT 1
- Problem with compilation in Mac OS HOT 1
- Lack of installation requirements HOT 2
- How to install HOT 3
- Dependencies broken for submodules HOT 3
- Error: Assertion `thread::has_threads()' failed. HOT 1
- Amazing HOT 1
- invalid function sinh and others
- Same issue but for exp2 HOT 1
- Add License HOT 1
- Installation on windows HOT 2
- Add docker image
- SLN File no longer compiles HOT 2
- feature request: erfc() and expm1() HOT 4
- Using lolremez to find half precision polynomials or arbitrary bits precision fixed point HOT 1
- Higher precision for log(x) HOT 3
- Rational Approximation? HOT 1
- Doesn't build with clang
- The Dockerimage fails to build.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from lolremez.