Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2012-04-10 06:51:53

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

PSLQ and LLL?

Hi guys

Anyone mind explaining how to use these two algorithms,for which I understand are useful for finding integer relationships between numbers. Can anyone show me how to use these on an example?

Last edited by anonimnystefy (2012-04-10 06:52:55)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#2 2012-04-10 07:43:59

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

Hi;

The coding is difficult and can be found on the internet. You will find it is full of bugs.

I have been using PSLQ and LLL to solve your puzzles. It has been about 50% effective.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#3 2012-04-10 07:45:51

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

Hi bobbym

I know both. But can you show me what the algorithm actually doess?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#4 2012-04-10 07:53:36

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

To demonstrate it requires a computer. It is not a hand method. I already have a whole thread on this in the computer math thread.

I can give a small toy example if you wish.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#5 2012-04-10 07:55:27

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

If you mean the one where you showed this to gAr,then I saw that one,but couldn't get any of it.

Yes a small example will be just fine. Let me see if I can go on my laptop.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#6 2012-04-10 08:07:55

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

That is your input vector. The first element is the number you wish to find an integer relation for in terms of the others. You do the first run with 15 digits of precision.

You get:

Then you do another run with 25 digits of precision ( commion move in numerical analysis ), you get:

The top row has the smallest coefficients and is the answer.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#7 2012-04-10 08:08:49

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

That is your input vector. The first element is the number you wish to find an integer relation for in terms of the others. You do the first run with 15 digits of precision.

You get:

Then you do another run with 25 digits of precision ( common move in numerical analysis ), you get:

The top row has the smallest coefficients and is the answer.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#8 2012-04-10 08:15:01

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

hi bobbym

Does that mean that

?Because that is not true!

Last edited by anonimnystefy (2012-04-10 08:16:07)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#9 2012-04-10 08:18:02

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

Hi;

Close. It takes a little time to get used to it.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#10 2012-04-10 08:18:54

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

That is the same,but why is there -1 in the first row vector?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#11 2012-04-10 08:22:27

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

Everything in the vector after the first is a number that we are trying to fit that constant on the left with. I will demonstrate with another toy example.

Solve 3x + 5y = 21


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#12 2012-04-10 08:25:00

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

Hi bobbym

What does PSQL actually do with the numbers? Or is that just too complicated?

A for that one,we probably input the vector:

Last edited by anonimnystefy (2012-04-10 08:29:00)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#13 2012-04-10 08:28:44

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

That's is correct. One of its answers will be x = 2 and y = 3.

It is essentially black box and entirely a computer technique. The good thing is you do not always have to understand something to use it!


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#14 2012-04-10 08:30:58

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

I don't understand many things I use,but I always try to understand at least a bit.But I wont insist on it.

Do you have your code for PSQL? And which languages can it be programmed in?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#15 2012-04-10 08:33:01

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

I use it in mathematica, maple has a better one built in. Sage has a good one. I do not know about maxima.

I wrote my own in mathematica code.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#16 2012-04-10 08:35:10

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

I know you wrote your own code,but how can I program in Maxima?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#17 2012-04-10 08:38:01

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

Do you have maxima?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#18 2012-04-10 08:38:38

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

Yes I do.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#19 2012-04-10 08:40:43

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

Do you know how to program in it?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#20 2012-04-10 08:44:11

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

No,I need help.First of all there are two programs that use maxima on my desktop.One is wxMaxima and the other one is XMaxima.Which one should I write the code in?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#21 2012-04-10 08:46:00

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

I have no idea. I have not used the standalone maxima for many years and do not remember.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#22 2012-04-10 08:54:32

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

Could you check out somewhere,because I am clueless.

Will you be here in half an hour or so?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#23 2012-04-10 08:55:37

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

I will be here.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#24 2012-04-10 08:55:59

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,544

Re: PSLQ and LLL?

Ok.I will be back in around half an hour,maybe less. smile


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#25 2012-04-10 09:09:21

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 87,164

Re: PSLQ and LLL?

I will take a break and get some air.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

Board footer

Powered by FluxBB