SourceForgeLogo

GLUCAS - Yet Another FFT

UPDATED: JUN-29-2002

Introduction                    Introducción (Español)

Project status

Downloads

Old Binaries

Documentation


INTRODUCTION.

Glucas is a free program to test primality of Mersenne numbers (numbers with the form 2^n - 1). Its results say us whether a Mersenne number is a prime number. You can learn a lot of Mersenne numbers here . The special form of Mersenne Numbers gives us three big advantages:

1) There is a fast test (Lucas-Lehemer test.). If success then we are sure the analyzed number is a Prime number. If fails then we are sure the number is not prime.

2) The modular reduction we need can be made in a easy way.

3) The algorithm used to multiply the very big numbers we usually need (about some million bits) uses a special form of Fast Fourier Transform, DWT. The speed are twice the general integer multiplication via FFT and convolution theorem.

These advantages make the records list of big prime numbers leaded by Mersenne Primes. You can be a discoverer of a record Mersenne Prime number. But don't be excited, it is very hard. There is a project in the Internet dedicated to the search of such scarce numbers. This is GIMPS, the Great Internet Mersenne Prime Search . GIMPS already has found the four biggest primes in the history and is one of the pioneers in the distributed computing in the net. The core of this project is G. Woltman, who wrote the client programs for x86 platforms. They are astonishing fast and I personally think is the fastest FFT ever written to these processors. They are carefully tuned in assembler.

Glucas is a c-coded program to make Lucas-Lehmer test. As I have old Pentiums at home and work, I also included some assembler macros for GNU/gcc compiler to speed it up. I've reached about 80% of Woltman's latest prime95 v.20. For other platforms there is only two clients available fast enough, Glucas and Mlucas. Mlucas is an excellent fortran90-coded program written by E.W. Mayer (a version of Mlucas is included in the test suite specf2000). The performance of Mlucas is similar to Glucas. Mlucas needs a good f90 compiler and Glucas a C-compiler. For some platforms as Mac, there is no f90 compilers available, and here is the advantage of Glucas.

You can read more about Glucas. The complete manual online is here. You also can get the printable dvi manual.

YEAFFT is the library used by Glucas to make the convolutions (big multiplications) we need. This is written by Guillermo Ballester Valor (me) and the skeleton is based in this paper. This is a C-coded library with some assembler macros for GNU/gcc compiler. It is written under GPL license.




INTRODUCCIÓN

Glucas es un programa de código abierto y gratuito para realizar el test primalidad de los números de Mersenne (números de la forma 2^n - 1). Sus resultados nos dicen si un número de Mersenne es un número primo. Puede leer más acerca de los números de Mersenne aquí. La forma especial de los números de Mersenne ofrece tres grandes ventajas:

1) Existe un test suficientemente rápido (test de Lucas-Lehmer). El resultado de dicho test es positivo si y solo si el número de Mersenne es primo.

2) La aritmética modular que se precisa en los cálculos puede realizarse de una forma sencilla sin tener que recurrir a costosas divisiones.

3) El algoritmo utilizado para multiplicar los números tan grandes que necesitamos (algunos millones de bits) utilizan una forma especial de Transformada Rapida de Fourier, DWT . La velocidad que se alcanza con esta Transformada es el doble de la forma general de multiplicar grandes enteros a traves de Transformadas Rápidas de Fourier y el teorema de convolución.

Estas ventajas hacen que la lista de records de grandes numeros primos esté liderada por los números de Mersenne. Usted puede ser el descubridor de un nuevo número primo de Mersenne record, pero no se haga ilusiones rápidamente, es bastante difícil. Hay un proyecto en Internet dedicado a la búsqueda de esos números tan escasos. Este proyecto es GIMPS, the Great Internet Mersenne Prime Search . GIMPS ya ha descubierto los cuatro números primos más grandes de la historia y es un proyecto pionero en el cálculo distribuido por Internet. El núcleo del proyecto es G.Woltman, quien ha escrito los programas clientes para la plataforma X86. Sus programas son desconcertantemente rápidos, y pienso que es la transformada rápida de Fourier más rápida que se ha escrito para dicha plataforma. Esta escrita cuidadosamente optimizada en lenguaje ensamblador.

Glucas es, en cambio, un programa escrito en C diseñado para realizar el test de Lucas-Lehmer. Como yo todavía trabajo con antiguos pentiums en casa y en el trabajo, también he incluido algunas macros en ensamblador para esta plataforma utilizando el excelente compilador GNU/gcc. Se ha alcanzado un 80% de la velocidad de la última version publicada de G.Woltman (prime95 v.20). Para otras plataformas solamante hay dos clientes suficientemente rápidos, Glucas y Mlucas. Mlucas es un excelente programa escrito en fortran-90 escrito por Ernst W. Mayer (una adaptación de Mlucas se utiliza en el test specf2000). La velocidad de Mlucas es similar a Glucas. Mlucas necesita un compilador f-90 y Glucas un compilador C. Para algunas plataformas como MAC, no hay buenos compiladores fortran-90 disponibles y aquí radica la ventaja de Glucas.

Puede leer más acerca de Glucas. Tiene a su disposición el manual completo en línea aquí. También puede bajarse el manual imprimible en formato dvi.

YEAFFT es la librería utilizada por Glucas para las convoluciones (grandes multiplicaciones) que se necesitan. Esta escrita por mí, Guillermo Ballester Valor. Está basado este artículo . Es una librería escrita en C con algunas macros definidas en ensamblador . Se ha escrito bajo licencia GPL.