Project

General

Profile

Feature #1306

exgcd over integers (ZZ)

Added by John Abbott over 4 years ago. Updated about 2 months ago.

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
New Function
Target version:
CoCoALib-0.99880
Start date:
02 Sep 2019
Due date:
% Done:

20%

Estimated time:
Spent time:
1.95 h

Description

Implement a general extended gcd over the integers.
The idea is that the cofactors should be reasonably small.

Probable design:

L := [15,21,0,35];
exgcd(L);
record[gcd:=1, cofactors:=[1,1,0,-1]]

Name of record fields are "just a first guess".

Related issues

Related to CoCoALib - Feature #1227: exgcd; solve Bezout equationNew2018-09-19

History

#1 Updated by John Abbott over 4 years ago

#2 Updated by John Abbott over 4 years ago

The cofactors are defined only modulo the lattice of "syzygies" (kernel of the row matrix); the hope is that the vector produced is a small one (not nec. the smallest possible).

The function should not be too slow.

#3 Updated by Anna Maria Bigatti over 4 years ago

Name extgcd?
I prefer with the 't'

#4 Updated by John Abbott about 4 years ago

  • Status changed from New to In Progress
  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99800
  • % Done changed from 0 to 20

I have a first (untested) prototype. Maybe I'll test it tomorrow... too late now.

#5 Updated by John Abbott about 4 years ago

Currently it returns just the cofacs. I had hoped to avoid an include directive in the header file... not so easy.
The impl is correct, but tends to produce cofacs which are far too large (because I impl'ed a poor strategy).

Need to impl some better strategies!

#6 Updated by John Abbott about 3 years ago

The source code is in NumTheory-gcd.C.

#7 Updated by John Abbott about 2 years ago

  • Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850

#8 Updated by John Abbott about 2 months ago

  • Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880

Also available in: Atom PDF