[Agda] BF library announcement

Sergei Meshveliani mechvel at botik.ru
Fri May 3 15:36:16 CEST 2019


BFLib 0.1 -- a library of certified Agda programs for arithmetic of
             Binary Integer numbers and Generic Fractions
	      
is available on 

   http://www.botik.ru/pub/local/Mechveliani/bfLib/,
   ftp://ftp.botik.ru/pub/local/Mechveliani/bfLib/,
   https://github.com/mechvel/BFLib-0.1

(see license.txt in the archive).


BFLib-0.1  is a pure, regular-performance, complete, and certified 
           binary arithmetic for  integer numbers,  and the arithmetic
           of  fractions  in the general case of fractions over an
	   arbitrary GCDRing.

It has been tested under  Agda 2.6.0, MAlonzo, ghc-8.6.3.

It is suggested as a replacement (with possible changes) for the  Bin and
Rational parts  in  Standard library lib-1.0.

BFLib suggests the three improvements.
(I) Essentially faster implementation for `<-cmp', show, gcd for Nat,
    and for arithmetic of rational numbers.
(II)  New Bin part.
(III) Generic Fraction domain constructor. 

The Bin part of the library improves the Standard library in three ways.
* It has many operations and proofs that are important and necessary and
  are missed in standard.
* Its arithmetic has a reasonable cost order even for the case when the
  proof parts are inspected.

The Fraction part of the library improves the standard library in that
fractions are considered not only over integer numbers, but over an
arbitrary GCDRing. So that the domain Rational is expressed as
(Fraction Integer). And many other kinds of fractions become possible to
operate with, for example, fractions of multivariate polynomials.
In particular, the domain  BRational = Fraction BInteger  provides arithmetic
for rational numbers which parts are represented in binary system,
which arithmetic has a low cost order.


Relation to Standard library lib-1.0
------------------------------------
* The Bin part is completely replaced.
* The classical generic algebra structure hierarhy  (Setoid, Magma, ...,
  CommutativeRing) is taken of  standard library.
  And for the Fraction part, there are added the following items.
a) DecIntegralRing (a commutative ring without zero divisors and with a
   decidable division),  GCDRing -- a DecIntegralRing which provides the gcd
   operation.
b) A general definition of  primality  and  greatest common divisor.

Concerning the Bin part:
------------------------
the binary representation for natural numbers is by the constructors:
0#, 2suc, suc2* (zero, any even, any odd).
It follows the respresentation that was shown in 2016 in the library by 
Martin Escardo of 2016:
       http://www.cs.bham.ac.uk/~mhe/agda-new/BinaryNaturals.html

The Bin part is mainly Binary-4  (https://github.com/mechvel/Binary-4),
with a certain improvement for the _<_ relation.


Installation:
              agda -c $agdaLibOpt TypeCheckAll.agda
              agda -c $agdaLibOpt Bin/GCDTest.agda
	      agda -c $agdaLibOpt Fraction/BRationalTest.agda

Performance tests:
  Bin/DivModTest.agda, Bin/GCDTest.agda, Bin/LogarithmTest.agda,
  Fractions/BRationalTest.agda, Fractions/RationalTest.agda.
  ("readme"-s are included). 

Memory requirement
------------------
Type checking BFLib needs at list  900 Mb RAM.
This also suffices to compile it via the MAlonzo tool.
To work with BFLib it is desirable to have at least 4 Gb computer. 

Comments and improvements are welcome.

---------------------
Sergei D. Meshveliani



More information about the Agda mailing list