Sieves

Author(s): Iannis Xenakis and John Rahn

Source: Perspectives of New Music, Vol. 28, No. 1 (Winter, 1990), pp. 58-78
Published by: Perspectives of New Music
Stable URL: http://www.jstor.org/stable/833343
Accessed: 02/08/2010 07:55

Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at
http://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR's Terms and Conditions of Use provides, in part, that unless
you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you
may use content in the JSTOR archive only for your personal, non-commercial use.

Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at
http://www.jstor.org/action/showPublisher?publisherCode=pnm.

Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed
page of such transmission.

JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of
content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms
of scholarship. For more information about JSTOR, please contact support@jstor.org.

Perspectives of New Music is collaborating with JSTOR to digitize, preserve and extend access to Perspectives
of New Music.

http://www.jstor.org
 SIEVES

t &tr

IANNISXENAKIS

IN MUSIC, the question of symmetries (spatial identities) or of peri-

odicities (identities in time) plays a fundamental role at all levels, from
the sample, in sound synthesis by computer, to the architecturesof a piece.'
It is thus necessary to formulate a theory permitting the construction of
symmetries which are as complex as one might want, and inversely, to
retrieve from a given series of events or objects in space or time the
symmetries that constitute the series. We shall call these series "sieves."
Everything that will be said here could be applied to any set of charac-
teristics of sound or of well-ordered sonorous structures, and especially to
any group furnished with an additive operation and whose elements are
multiples of a unity, that is to say that they belong to the set N of natural
numbers. For example: pitches, time-points, loudnesses, densities, degree
of order, timbres locally, and so on. In the case of pitches, there must be a
 Sieves 59

distinction between sieve and mode. Indeed the white keys on a piano
constitute a unique sieve (scale) upon which are formed the "modes" of C
major, D, E, G, A (natural minor), etc. Just like Indian ragas or Olivier
Messiaen'smodes "of limited transposition," modes are defined by melodic
formulas, cadential formulas, harmonic formulas, and so forth.
But every well-ordered set can be represented as points on a line, if it is
given a referencepoint for the origin and a length u for the unit distance,
and this is a sieve.2

CONSTRUCTIONOF A SIEVE

Starting from symmetries (repetitions), let us construct a sieve (scale). As a

melodic example, we shall construct the diatonic scale formed by the white
keys of the piano.
With u = one semitone = one millimeter and a zero reference point
taken arbitrarilyon a note, for example C3, we can notate the diatonic sieve
(scale) on graph paper scaled to the millimeter, by means of points to the
left and to the right of that zero reference point with successive intervals
from left to right of 2, 2, 1, 2,2,2, 1,
2,2,2, , 2, 1,.. .millimeters, or we
can write the sieve in a logical-arithmeticnotation as L = 120 U 122 U 124
U 125 U 127 U 129 U 1211 where 12 is the modulus of symmetry (period)
of the octave and u is the semitone. This notation gives all the Cs, all the
Ds, ... all the Bs, considering that the moduli 12 repeat on both sides of the
zero reference point. The indices 0, 2, 4, 5, 7, 9, 11 of the modulus 12
signify shifts to the right of the zero of the modulus 12. They thus
represent the residue classes of congruence mod 12. With a different unit
distance u, for examplethe quartertone, one would have the same structure
as the diatonic scale but the period of the series would no longer be the
octave, but the augmented fourth.
In a similar fashion, a periodic rhythm, for example (3,2,2)= J . JJ|
can be notated as L = 70 U 73 U 75. In both of these examplesthe sign U
is a logical union (and/or) of the points defined by the moduli and their
shifts.
The periodicity of the diatonic sieve is external to it and is based on the
existence of the modulus 12 (the octave). Its internal symmetry can be
studied in the indices i (offsets, residue classes) of the terms 12i. But it
would be interesting to give, when it exists, a more hidden symmetry
derived from the decomposition of the modulus 12 into simpler moduli
(symmetries, periodicities), such as 3 and 4, a decomposition which would
have the advantage of allowing a comparison among different sieves in
order to study the degree of their difference and to be able to define a
notion of distance in this way.3
60 of NewMusic
Perspectives

Let us take the elementary sieves 30 and 40. In taking the points 30 and/
or the points 40 we obtain a series H1 = {..., 0, 3, 4, 6, 8, 9, 12, 15, 16,
18, 20, 21, 24, 27, 28, ...} = 30 U 40, and if C is the zero and u = one
semitone, H1 becomes { ..., C, D", E, F?, GO,A, C, DP, E, ... }. But if we
take the points common to 30 and 40 we obtain the series H2 = { ..., 0,
12, 24, 36, ...} = 30 n 40 where the sign n is the logical intersection
(and) of the sets of points defined by these moduli and their respective
offsets.
Hence we observe that the seriesH2 can be defined by the modulus 12 =
3 * 4 and by the logical expression L = 120 which gives the octaves. The
number 12 is the smallest common multiple of 3 and 4, which are coprime,
that is, their largest common denominator is 1.4
Let us imagine now the elementarysieves 20 and 60. Then G1 = 20 U 60
= {..., 0, 2, 4, 6, 8, 10, 12,...} and the common points are G2 = 20 n 60
= {..., 0, 6, 12, 18,... }. But here, the series is no longer made into octaves
as in the preceding case.
To understand this, let us take another example with elementary moduli
M1 = 6 andM2 = 15 which have been adjusted to the origin. Form the
pairs 60 = (M1, I1) and 150 = (M2, 12) with l = 0 and 2 = 0 as indices.
The series of the union (M1, I1) U (M2, 12) = K1 will be K1 = {..., 6,
12, 15, 18, 24, 30, 36, 42, 45,...} and their common points (the intersec-
tion) will form the series (M1, I1) n (M2,12) = K2, where K2 = {..., 0,
30, 60, ...}. The period is clearly equal to 30, the largest common
denominator D of 6 and 15 is the 3 (which is, by multiplication, the part
congruent to M1 and M2), and the smallest common multiple M3 equals
30. Now 6 divided by the largest common denominator D equals 2 equals
C1 and 15 divided by the largest common denominator D equals 5 equals
C2. Generalizing, the period of the points common to two moduli M1 and
M2 will be the smallest common multiple M3 of the two moduli, so (M1,
I1) n (M2, 12) = (M3,13) with 13 = 0, ifll = 12 = 0 andM3 = D C1
C2, where C1 = M1/D and C2 = M2/D.
Thus it is seen that the operation of logical union, notated as U, of two
elementary moduli M1 and M2 is cumulative in that it takes into account
the periodic points of both moduli at once. In return, the logical operation
of intersection, notated n, is reductive since we take only the points
common to both moduli.
When we mix the points of severalmoduli M1, M2, M3, M4 ...:

(a) by union, we obtain a sieve which is dense and complex depending on

the elementary moduli,

P1 = (M , I1) U (M2,12) U (M3,13) U...

 Sieves 61

(b) by intersection, we obtain a sieve which is more rarifiedthan that of the

elementary moduli, and there would even be some cases in which the
sieve would be empty of points since it lacks coincidences,

P2 = (M1, I1) n (M2,12) n (M3,13) n...

(c) by simultaneous combinations of the two logical operations, we obtain

sieves which can be very complex,

(0) L = {(Mll, I) n (M12,112) n ...}

U {(M21, 21) n (M22, I22) n ...} U {(...)}
kO Ik(i)

i= 1 /
The intersection of each set of pairs between curly bracketsshould furnish
a single final pair, if it exists. The final pairs will be combined by their
union, which will furnish the desired sieve.
Now let us examine the rigorous formulation of the calculus of the
intersection of two moduli (M1, II) and (M2, 12) where the periods M1
and M2 start from some II and 12 respectively.First II and 12 are reduced
by taking their modulos with respect to M1 and M2, I1 = MOD(I1, M1)
and 12 = MOD(12, M2).5
The first coincidence will eventually appear at a distance:

(1) S = II + . -M1 = 12 + u *M2

where Xand r are elements of N, and if2M1 = D * C1 and M2 = D * C2

with D equal to the largest common denominator, C1 and C2 being
coprime, then the period M3 of the coincidences will be: M3 = D * C1 ?
C2. From (1) there follows:

11-12 = ( *D - C2-A *D * Cl and (I1-12)/D = * C2-X * Cl.

Now since the expression on the right of the equality is a whole number,
the left of the equality should be a whole number also. But if I1-12 is not
divisible by D (for some 1l, 12), then there are no coincidences, and the
intersection (Mi, II) n (M2, 12) will be empty. If not:

(2) (I1-12)/D = i E N and t = u C2-X * C1,

also J + K? C1 = a ? C2.

But following the theorem of Bachet de Meziriac (1624), if x andy are

62 of NewMusic
Perspectives

two coprimes, it is necessary and sufficient that there exist two relative
whole numbers t and t such that:

(3) ?
1+ .x = 5.y or 5' .x = 5'.y+ 1

where t and 5' come from the recursiveequations:

(4) MOD( .C2,C1)= 1

and

(5) MOD( ''C1,C2) I

while letting ~ and t' run through the successive values 0, 1, 2, 3,

... (except if Cl = 1 and C2 = 1).6
But since Cl and C2 are coprime, there follows from (2) and (3): XAli
=, cr/4 = t, X/(- 4) = ', and a/(- q) = 5',and if(M1, II) fl (M2,12)
(M3,13), then

(6) 13 = MOD((12 + .
(11-12) C2),M3)

or

13 = MOD((1I + t' *(12 -II) C1), M3)

with M3 =D*C1 C2.7

Example 1:M1 = 60, 11 = 18,M2 = 42, 12 = 48, D = 6, Cl = 10, C2

= 7 M3 = 6' 10 7 = 420, with Cl and C2 coprime. From (3) and (4)
we get 4' = 5. From (6) we get:

13 = MOD(18 + 5 . (48-18) - 10, 420) = 258.

= 8,12 3, D = 2, C1 = 3, C2 = 4,
Example 2: Ml = 6, 11 -
3,M2 =
M3 = 24, with Cl and C2 coprime. From (4) we get = 1I and from (6):

13 = MOD(3 + 1 (3 - 3). 4), 24) = 3,

that is, in the case that II = 12 then 13 = II = 12, and hereM3 = 24 and
13= 3.
Takethe preceding example but with II = 3 and 12 = 4 so Il is not equal
to 12. Then IIID = 1.5, which is not an element of N, so there are no
coincidences and M3 = 0 and 13 = 0. But if II = 2 and 12 = 16 so that
 Sieves 63

(I1-I2)/D = 7 E N, we obtain from (4) e = 1 and from (6) 13 = MOD(0

+ 1 (2-0) * 4, 24) = 8 and (M3, I3) = (24,8). (See Example 1.)

Given: M M2, Il, 1, 2, with Ii = MOD(I, Mi) > 0

D = the largest common denominator of MI and M2
M3 = the smallest common multiple of M1 and M2
C1 = M1ID , C2 = M2/D, M3 = D *C1 *C2

EXAMPLE 1: COMPUTATION OF THE INTERSECTION

(M1, I) n (M2, 2) = (M3, 3)
64 of NewMusic
Perspectives

To compute several simultaneous intersections (coincidences) from an

expression between bracketsin the equation (0) of L, it suffices to calculate
the pairs in that expression two by two. For example:
kO=4 k (i)\
L= Z I
i=l \ /
= {(3, 2) n (4, 7) n (6, 11) n (8, 7)} U {(6,9) n (15,18)} U {(13, 5)
n (8, 6) n (4, 2)} U {(6, 9) n (15, 19)}

For the first expression between bracketswe do at first (3, 2) n (4, 7) =

(12, 11), then, after modular reduction of the indices, (12, 11) n (6, 5) =
(12, 11), then (12, 11) n (8, 7) = (24,23). We go on to the following
brackets,and so on. Finally,

L = (24, 23) U (30, 3) U (104, 70) U (0, 0)

for kO= 4, k(l) = 4, k(2) = 2, k(3) = 3, k(4) = 2.

This logical expression will furnish us with the points of a sieve con-
structed in this fashion:

H = { ...3, 23, 33, 47, 63, 70, 71, 93, 95, 119, 123, 143, 153, 167,
...479, ...}

with a period of P = 1560. The zero of this sieve within the set of pitches
can be arbitrarilytaken to be C_2 = 8.25 Hz and at ten octaves, (210 * 8.25
= 16384 Hz) with u equal to the semitone. It will give us the notes D- _2,
B_1, Ao, B1, Dt3, At3, B3, A5, C6, B7....
For the same zero and for u equal to a quartertone the series gives us the
notes CO_2, B_ -2, E -1, B t 1, G 0, Bo, B o, A#l, B t i, B 2,
C#3 ....

INVERSECASE

Let us start from a series of points either given beforehand or constructed

intuitively and deduce its symmetries, that is to say the moduli and their
offsets, (Mj, IJ), and construct the logical expressionL describing this series
of points. The steps to follow are:

(a) Each point is considered as a point of departure (= In) of a modulus.

 Sieves 65

(b) To find the modulus corresponding to this point of departurewe begin

by applying a modulus of value Q = 2 unities. If each one of its
multiples meets a point which has not already been encountered and
which belongs to the given sieve, we keep the modulus and it forms the
pair (Mn, In). But if any one of its multiples happens not to correspond
to one of the points of the series, we abandon it and pass on to Q + 1.
We proceed so until each one of the points in the given series has been
taken into account.

(c) If for a given Q we garner all its points (Q, Ik) under another pair (M,
I), that is if the set (Q, Ik) is included in (M, I), then we ignore (Q, 1k)
and pass on to the following point I(K + 1).

(d) Similarly,we ignore all the (Q, I) which, while producing some of the
not-yet-encountered points of the given series, also produce, upstream
of the index I, some parasitical points other than those of the given
series.

An example:the preceding seriesH, taken only between the points 3 and

16, could be constructed by this union:

L = (73, 70) U (30,3) U (24, 23),

with P = 8760 as its period. While if the same series H were limited
between the points 3 and 479 (this time having 40 points), it would be
generated by

L = (30, 3) U (24, 23) U (104, 70),

the modulus 30 covering 16 points, the modulus 24 covering 20, and

modulus 104 covering 4 points. The function L is identical to that given
earlier.Its period is P = 1560.
In general, to find the period of a series of points derived from a logical
expressionwhose final form is the union of moduli (Mj, Ij), it is enough to
compose the intersection of the moduli within the parenthesestwo by two.
For example: M1 = 12,M2 = 6,M3 = 8;M1 lMn 2 = D C1 C2 = 6 2
1 = 12 = M; M n M3 = D * C1 * C2 = 4 * 3 * 2 = 24. And the period P
= 24. In general one should take into account as many points as possible.
The more points of a given series are taken into account, the more the
logical expressionL is precise.
66 of NewMusic
Perspectives

HYPERBOLAE OF SIEVES

Hyperbolae (transformations)of sieves can come about in various ways:

(a) by a change of the indices of the moduli. For example:L = (5, 4) U (3,
2) U (7,3) of periodP = 105 will give the seriesH = {..., 2, 3, 4, 5, 8,
9, 10, 11, 14, 17, 19, 20, 23, 24, 26, 29, 31,...}. But if a whole
number n is added to the indices, the expressionL becomes for n = 7,
L' = (5, 11) U (3, 9) U (7, 10) and after modular reduction of the
indices, L' = (5, 1) U (3, 0), U (7, 3), of the same period P = 105. The
series H' = {..., 0, 1, 3, 6, 9, 10, 11, 12, 15, 16, 17, 18, 21, 14, 16, 17,
30,...}, derived from the last expression L', has the same intervallic
structure as the H series and differs from it only by its initial point,
which is given by the smallest index of the expression L' and by an
offset n of the intervallic structure of H. Indeed, if in series H you see
intervals start from 2, which is the index of the smallest modulus ofM,
the same intervals are seen to start from 2 + 7 = 9 within series H'.
This case is what musicians call "transposition"upwards and is part of
the technique of "variations."If on the other hand we add to each index
some whole number n, then the intervallic structure of the sieve
changes while its period is conserved. For example, add 3, 1, and -6
respectivelyto the three indices of L, which become after their modular
reductions L = (5, 2) U (3, 0) U (7, 4) of period P = 105, and which
gives H = {...,0, 2, 3, 4, 6, 7, 9,11,12, 15,17, 18, 21, 22, 24, 25, 27,
30, 32,...}.
(b) by transformationsof the logical operations in some fashion, using the
laws of logic and mathematics, or arbitrarily.

(c) by the modification of its unity u. For example, sing the national
anthem, which is based on the diatonic major subset (white keys), while
transforming the semitone into the quartertone or into the eighthtone,
and so on. If this alterationis used rarelymelodically or harmonically,it
has occurred in the other characteristicsof tone such as time since at
least prehistoric times, by changes of tempo.

CONCLUSION

In provisional conclusion, the theory of sieves studies the internal symme-

tries of a series of points either constructed intuitively,given by observa-
tion, or fabricatedcompletely by moduli of repetition.
In what has just been said, the examples have been taken from instru-
mental music. But it is quite conceivable to apply this theory to the
 Sieves 67

synthesis of sounds by computer, imagining the amplitude and/or the time

of the sound signal ruled by sieves. The fine symmetries thus created
should open a new field for exploration.

-translated by John Rahn

NOTES

1. Earlier articles on sieves by this author have appeared in Preuves

(November 1965), Paris; La Nef no. 29, (1967), Paris; Revue
d'Esthetique,21 (1968), Paris; Tempo93 (Summer 1970); and For-
malized Music (Bloomington, Indiana: Indiana University Press,
1971.) This new article is more complete and is followed by a
program in C.
2. Historically, the invention of the equal-tempered chromatic scale,
attributed to the Renaissance, is of capital importance, because it
provided the pitch domain with a universal standard, quite fecund,
comparable to the already established one in rhythm. However, the
first theoretical attempt of such a procedure, which opens up the way
to number theory in the pitch domain, was inaugurated by Aristo-
xenos of Tarentin the fourth century B.C. with his "Harmonics."
As for rhythm outside Western civilization, see "Du pied a la main:
les fondements metriques des musiques traditionnelles d'Afrique
centrale" by Simha Arom, in Analyse Musicale 10 (January 1988):
16-22.
3. See note 7.
4. Euclid's algorithm. Let, x be two positive whole numbers. Begin by
letting D = MOD(y,x), then replacey with x and x with D. If D is
not equal to 0 then start over. But if D = 0 then the last y is the lar-
gest common denominator. Call thisy, D. (See the following figure.)
68 of NewMusic
Perspectives

taketwo numbers:y, x
1. -*D - MOD (y,x)
2. y- x, x-D
3. -yes-<D $ 0>-no-i

ID.-y
| END I

example:y = 30, x = 21
- MOD(21,9) = 3 -
D -MOD(30,21)=9 D- D MOD(9,3) = 0
y4-21,x -9 y-9,x-3 yD3,x0-
D=90 0 ~=9^0 D=3^0.D=O
D = 30 0 therefore,
therefore,
D-(y= 3)
END

5. a modulo b, notated MOD(a, b), is equal to the residue of the

division of a by b: a/b = e + r/b where r is this residue, if a, b, e, and r
are elements of N.
6. MOD(t * C2, C1) = 1 represents the integer equation: ~ * C2/ C1 = v
+ 1/Cl.
7. Let there be (M, I) with M a composite of the form M = mk * n1...
* ri. It is sometimes necessary and possible to decompose it into
(mk, Im) n (nl, I.) n... (ri, Ir) = (M, J).
 Sieves 69

CRIBLES; guide d'utilisation des programmes

A. GENERATION DE POINTS SUR UNE DROITE A PARTIR DE LA

FORMULELOGIQUE DU CRIBLE

Exemple:
DEFINITION D'UN CRIBLE:
L = ()* ( * ... * )
*
+ [() * () ... * ()]

Dans chaque parenthese on a dans l'ordre: module, point de depart

(pris dans l'ensemble des entiers)
[] + [] designe une union
() * () designe une intersection

A partir de la formule d'un crible compose d'unions et

d'intersections de modules, le programme reduit les
intersections et ne conserve que les unions.
Les abscisses des points du crible issus de ces unions sont
ensuite calcules.

NOMBRED'UNIONS ? = 2

union 1: nombre de modules ? = 2

module 1 ? = 3
debut ? = 2

module 2 ? = 4
debut ? = 7

union 2: nombre de modules ? = 2

module 1 ? = 6
debut ? = 9

module 2 ? = 15
debut ? = 18

FORMULEDU CRIBLE:

L = C ( 3, 2) * ( 4, 7) 3
+ C ( 6, 9) * ( 15, 18) ]

REDUCTION DES INTERSECTIONS:

union 1
[ (3,2) * (4,7) ] = (12,11)

decomposion en modules premiers entre eux ?

(appuyez sur 'o' si oui; sinon appuyez sur une autre touche): o

(12,11) = (4,3) * (3,2)

union 2
[ (6,9) * (15,18) ] = (30,3)

decomposion en modules premiers entre eux ?

(appuyez sur 'o' si oui; sinon appuyez sur une autre touche): o

(30,3) = (2,1) * (3,0) * (5,3)

70 of NewMusic
Perspectives

FORMULEDU CRIBLE REDUITE A DES UNIONS:

L = ( 12, 11) + ( 30, 3)

POINTS DU CRIBLE ISSUS DE CETTE FORMULE:

rang de scrutation des points ? = 0
frappez <enter> pour obtenir a chaque fois une serie de 10 points

Rang des
dizaines
0 3 11 23 33 35 47 59 63 71 83
10 93 95 107 119 123 131 143 153 155 167
20 179 183 191 203 213 215 227 239 243 251
30 263 273 275 287 299 303 311 323 333 335
40 347 359 363 371 383 393 395 407 419 423
50 431 443 453 455 467 479 483 491 503 513
60 515 527 539 543 551 563 573 575 587 599
70 603 611 623 633 635 647 659 663 671 683
80 693 695 707 719 723 731 743 753 755 767
90 779 783 791 803 813 815 827 839 843 851
100 863 873 875 887 899 903 911 923 933 935
110 947 959 963 971 983 993 995 1007 1019 1023
120 1031 1043 1053 1055 1067 1079 1083 1091 1103 1113
130 1115 1127 1139 1143 1151 1163 1173 1175 1187 1199

B. GENERATION DE LA FORMULELOGIQUE DU CRIBLE A PARTIR

D'UNE SERIE DE POINTS SUR UNE DROITE

Exemple:
A partir d'une suite de points donnes, trouver les points de
depart et leurs modules (periodes).
NOMBREDE POINTS DU CRIBLE ? = 12

abscisses des points:

point 1 = 59 point 2 = 93 point 3 = 47 point 4 = 3

point 5 = 63 point 6 = 11 point 7 = 23 point 8 = 33
point 9 = 95 point 10 = 71 point 11 = 35 point 12 = 83
POINTS DU CRIBLE (abscisses dans l'ordre croissant):

Rang des:
dizaines
0 3 11 23 33 35 47 59 63 71 83
10 93 95

FORMULEDU CRIBLE:
dans chaque parenthese on a dans l'ordre:
(module, point de depart, nombre de points couverts)
L = ( 30, 3, 4) + ( 12, 11, 8)

periode du crible: P = 60
 Sieves 71

CEMAMu A. GENERATION OF POINTS ON A STRAIGHT LINE FROM

crb. c THE LOGICAL FORMULA OF THE SIEVE

Line# Source Line

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <conio.h>
4
5 /* ---------------- types definitions ----------------------------------- */
6 typedef struct /* period ( congruence class ) */
7 {
8 short mod; /* modulus of the period */
9 short ini; /* starting point */
10 } periode;
11 typedef struct /* intersection of several periods */
12 {
13 short clnb; /* number of terms in the intersection */
14 periode *cl; /* terms in the intersection */
15 periode clr; /* resulting period */
16 unsigned long ptval; /* current point value */
17 } inter;
18 /* ----------------- function prototypes ---------------------------------/
19 periode ReducInter(short u); /* computation of the intersections */
20 short Euclide(short ml,short m2); /* computation of the LCD */
21 short Meziriac(short cl,short c2); /* computation of "dzeta" */
22 void Decompos(periode pr); /* decomposition into prime factors */
23
24 /* ---------------- variables --------------------------------------- */
25 inter *fCrib; /* sieve formula */
26 short unb = 0; /* number of unions in the formula */
27
28 short uO, ul, u = 0; /* current union index */
29 short i = 0; /* current intersection index */
30 unsigned long lastval,n0,ptnb = 0;
31 periode CL_EMPTY = { 0, 0 }; /* empty period */
32
33 #define NONEMPTY 1
34 short flag = 0;
35 short decomp = 0;
36
37 * ========================================
38 void main(void)
39 {
40 printf("SIEVES: user's guide\n\n"
41 "A. GENERATION OF POINTS ON A STRAIGHT LINE FROM\n"
42 " THE LOGICAL FORMULAOF THE SIEVE\n\n"
43 "Example:\n"
44-----------------------------\n"
45 "DEFINITION OF A SIEVE:\n"
46" L = () * () * ..* ()\n"
47 + [( * ( * ... ()]\n"
48" + ... \n"
49" + C() * () *. * ()]\n\n"
50 "In each parenthesis are given in order: modulus, starting point\n"
51" (taken from the set of integers)\n"
52 "[] + [] is a union\n"
53 "() * () is an intersection\n\n");
54 printf ("-------------------------------- \n"
55 "Given the formula of a sieve made out of unions and\n"
56 "intersections of moduli, the program reduces the number of\n"
57 "intersections to one and keeps only the given unions.\n"
58 "Then, the abscissa of the final points of the sieve are\n"
59 "computed from these unions and displayed.\n\n");
60 /* ------------- get the formula of the sieve -----------------------/
61 while (unb == 0)
62 {
63 printf("NUMBER OF UNIONS ? = ");
64 scanf("%d",&unb);
65 }
66 fCrib = (inter *)(malloc (sizeof(inter) * unb));
67 if (fCrib == NULL)
68 {
69 printf("not enough memory\n");
70 exit(1);
71 }
72 printf("------------------------------- \n");
73 for (u = 0; u < unb; u++)
74 {
 72 of NewMusic
Perspectives

CEMAMu
crb. c

Line# Source Line

75 printf("union %d: number of modules 7 ", u + 1);

76 scanf ("%d",&fCrib[u].c1nbi;
77 printf("\n");
78 fCrib(u).cl = (periode *)(malloc (sizeofiperiodei * fCrib[u.)clnb));
79 if (fCrib[u].cl == NULL)
80 C
81 printf("not enough memory\n");
82 exit(l);
83 I
84 for Ci = 0; i < fCrib[uJ.clnb; i++)
85 C
86 printfi"\n modulus %d 7 = ", i + 1);
87 scanf("%d",&fCrib[u].cl[iJ.mod);
88 printf(" start 7
89 scanf("%d",&fCribul].cl[i. ini);
90
91 printf(------------------------------- \n);
92 }
93 /* ------------- reduction of the formula ----------------------------
94 printf (FORMULA OF THE SIEVE: \n\n"
95 L= [ ");
96 for Cu = 0; u < unb; u++)
97 C
98 if (u != 0)
99 printfC" + ( ");
100 for Ci = 0; i < fCrib[u].clnb; i++)
101
102 if (i != 0)
103
104 if Ci % 4 == 0)
105 printfi"\n "I;
106 printfC"* ");
107
108 printfC"C%5d,%5d) ', fCrib[u].cl[i].mod, fCrib[u].cl[i].inii;
109
110 printf
I C"I\n" I;
111
112 printf "------------------------------- \n;
113 printf("REDUCTION OF THE INTERSECTIONS:\n\n");
114 for Cu = 0; u < unb; u++)
115
116 printf("union %d\n [ ".,u + 1);
117 for Ci = 0; i < fCrib[u].clnb; i++)
118
119 printfC '(%d,%d) ", fCrib[u3.cl[i .mod, fCriblu3.cl[i .ini)
120 if (i != fCribEuJ.clnb - 1)
121 printfC"* ');
122 I
123 fCrib[u).clr = RedjcInterCu); 1* reduction of an intersection *1
124 printf("C = (%d,%d)\n\n", fCrib[u).clr.mod, fCrib(u).clr.ini);
125 printfC" decomposition into prime modules ?\n"
126 (press 'y' for yes, any other key for no): ");
127 if (getcheo) == 'y')
128
129 printf("\n\n C%d,%d)", fCrib[ul.clr.mod, fCribEu).clr.ini);
130 Decompos CfCribEul. clr);
131
132 else
133 printfC"\n\n');
134
135 printf"--------------------------------\n");
136 /* -------------- display the simplified formula ----------------------
137 printf("SIMPLIFIED FORMULAOF THE SIEVE: \n\n");
138 printfC" L = ");
139 for Cu = 0; u < unb; u++)
140 C
141 if Cu != 0)
142 C
143 if Cu % 4 == 0)
144 printfC"\n
145 printfC"+ ");
146
147 printfC"C%5d,%5d) ", fCrib[uJ.clr.mod, fCrib[u).clr.ini);
148
 Sieves 73

CEMAMu
crb. c

Line# Source Line

149 printf("\n----------------------------- \n);

150 /* -------------- points of the sieve ---------------------------------
151 printf("POINTS OF THE SIEVE CALCULATEDWITH THIS FORMULA:\n");
152 printf("rank of first displayed point ? =
153 scanf(`%lu",&n0);
154 nO = nO - nO % 10;
155 printf('\npress <enter> to get a series of 10 points\n\n"
156 "Rank V);
157 for (u = 0; u < unb; u++)
158 {
159 if (fCrib[u].clr.mod != 0 :: fCrib[u].clr.ini = 0)
160 f
161 fCrib[ul.ptval = fCrib[u3.c1r.ini;
162 flag = NONEMPTY;
163 1
164 else
165 fCribEu].ptval = OxFFFFFFFF;
166 1
167 if (flag != NONEMPTY)
168 return;
169 uO = ul = 0;
170 lastval = OxFFFFFFFF;
171 while (1)
172 {
173 for (u = (uO + 1) % unb; u != uO; u = (u + 1) % unb)
174 (
175 if (fCrib(ul.ptval <= fCrib[u1].ptval)
176 ul = u;
177 1
178 if (fCribEul).ptval != lastval) 1* new point *1
179 f
180 lastval = fCrib(ul1.ptva1;
181 if (ptnb >= nO)
182 {
183 if (ptnb % 10 == 0)
184 {
185 getch(); /* get a character from the keyboard *1
186 printf("\n%71u :", ptnb);
187 1
188 printf("%6lu ", fCrib[ul].ptval);
189 1
190 ptnb++;
191 1
192 fCrib[ul).ptval += fCrib[u1J.c1r.mod;
193 uO = ul;
194 1
195 1
196 -
-====/* reduction of an intersection - *1
197 periode ReducInter(short u)
198 {
199 periode cl,cllc12,c13;
200 short pgcd,T,n;
201 long cl,c2;
202
203 c13 = fCrib[uJ.clEO);
204 for (n 1; n < fCrib[u).clnb; n++)
205 {
206 cl = c13;
207 c12 fCrib(u).cl(nJ;
208 if (cll.mod < cl2.mod)
209 (
210 cl = cll;
211 cll = c12;
212 c12 = cl;
213 1
214 if (cll mod 0 && c12.mod 0)
215 (
216 cll. i %= c1l.mod;
217 c12.ini %= c12.mod;
218 1
219 else
220 return CL-EMPTY;
221 /* module resulting from the intersection of 2 modules *1
222 pgcd = Euclide(cli.mod, c12.mod);
 74 of NewMusic
Perspectives

CEMAMu
crb. c

Line# Source Line

223 cl = cll.mod / pgcd;

224 c2 = c12.mod / pgcd;
225 if (pgcd != 1
226 && ( (cll.ini - cl2.ini) % pgcd 0 ))
227 return CL.-EMPTY;
228 if (pgcd != 1
229 && ((cll. mi - cl2.ini) % pgcd 0)
230 && (cll.ini - cl2.ini) && (ci c2)
231
232 c13.mod = pgcd;
233 c13.ini = cl. ini;
234 continue;
235
236 T = Meziriac((short) ci, (short) c2);
237 cl3.mod = (short) (cl * c2 * pgcd);
238 c13.ini = (short) (( cl. ini
239 + T * (cl2.ini - cll.ini) * ci) % cl3.mod);
240 while (cl3.ini < cll-ini c13.ini < c12.ini)
241 cl3.ini += cl3.mod;
242
243 return c13;
244

245 /*-decomposition into an intersection ========= */

246 /* of prime modules
247 void Decompos (periode pr)
248
249 periode pf;
250 short fct;
251
252 if (pr.mod 0)
253
254 printf(" (%d,%d)\n", pr.mod, pr.ini);
255 return;
256
257 printf(" =);
258 for ( i = 0, fct 2; pr.mod != 1; fct++)
259
260 pf.mod = 1;
261 while (pr.mod % fct == 0 && pr.mod 1)
262
263 pf.mod * fct;
264 pr.mod / fct;
265
266 if (pf.mod 1)
267
268 pf.ini = pr.ini % pf.mod;
269 pr.ini % pr.mod;
270 if (i = 0)
271 printf( *");
272 printf(" (%d,%d)", pf.mod, pf.ini);
273 i++;
274
275
276 printf("\n");
277

278 1* Euclide's algorithm *1

279 short Euclide (al, a2) 1* al >= a2 > 0 *1
280 short al;
281 short a2;
282 {
283 short tsp;
284
285 while ((tsp = al % a2) != 0)
286 I
287 al a2;
288 a2 = tsp;
289
290 return a2;
291

292 *- De Meziriac's theorem ===== -*1

293 short Meziriac (ci, c2) 1* ci >= c2 > 0 */
 Sieves 75

CEMAMu
crb. c

Line# Source Line

294 short cl;-
295 short c2;
296 {
297 short T = 0;
298
299 if (c2 == 1)
300 T = 1;
301 else
302 while (((++T * cl) % c2) != 1)
303
304 return T;
305 }
 76 of NewMusic
Perspectives

CEMAMu B. GENERATION OF THE LOGICAL FORMULA OF A SIEVE

pr. c FROM A SERIESOF POINTS ON A LINE

Line# Source Line

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string. h>
4 #include <conio.h>
5
6 /* -------------- definitions de types ------------------------------ */
7 typedef struct /* periode (classe de congruence) */
8 {
9 short mod; /* module de la periode */
10 short ini; /* point initial */
11 short couv; /* nombre de points couverts */
12 } periode;
13
14 /* --------------- prototypes de fonctions -----------------------------/
15 unsigned long Euclide(unsigned long ml,
16 unsigned long m2); /* calcul du PGCDde 2 nombres */
17
18 / ---------------- variables et constantes -----------------------------*/
19 periode *perCrib; /* periodes du crible */
20 short perTotNb = 0; /* nombre de periodes dans la formule */
21 long *ptCrib; /* points du crible */
22 long *ptReste; /* points non encore generes par une
23 periode */
24 short ptTotNb = 0; /* nombre de points dans le crible */
25 short p,ptnb,pmin,pmax;
26 long ptval;
27 unsigned long percrib;
28
29 periode per;
30
31 #define NON.REDONDANT 0
32 #define REDONDANT 1
33 #define COOVERT -32768
34 short flag;
35
36 ===================== == fonction principale ========================*/
37 void main(void)
38 {
39 printf("B. GENERATION DE LA FORMULE LOGIQUEDU CRIBLEA PARTIR\n"
40 " D'UNE SERIE DE POINTS SUR ONEDROITE\n\n"
41 "Exemple:\n"
42----------------------\n"
43 "A partir d\'une suite de points donnes, trouver les points de\n"
44 "depart et leurs modules (periodes).\n\n");
45 /* ------------- acquisition et tri des points du crible ------------ /
46 while (ptTotNb == 0)
47 {
48 printf("NOMBRE DE POINTS DU CRIBLE? = ");
49 scanf("Xd",&ptTotNb);
50 printf("%d\n",ptTotNb);
51 }
52 ptCrib = (long *)(malloc (sizeof(long) * ptTotNb));
53 ptReste = (long *)(malloc (sizeof(long) * ptTotNb));
54 perCrib = (periode *) (malloc (sizeof(periode) * ptTotNb));
55 if (ptCrib == NULL :: ptReste == NULL :: perCrib == NULL)
56 {
57 printf("memoire insuffisante\n");
58 exit(l);
59 }
60 printf("------------------------------- \n"
61 "abscisses des points:\n");
62 for (p = 0; p < ptTotNb; p++)
63 {
64 if (p % 4 == 0)
65 printf("\n ")
66 printf("point %d = "p + 1);
67 scanf ("ld", &ptval);
68 printf("%ld ", ptval);
69 for (ptnb = 0;
70 ptnb < p.&& ptval > ptCribEptnb];
71 ptnb++)
72
73 if (ptnb < p)
74 {
 Sieves 77

CEMAMu
pr. c

Line# Sou rce Line

75 if (ptval < ptCrib(ptnbJ) /* nouveau point */

76 memmove(&ptCribfptnb + 1J, &ptCrib[ptnb),
77 sizeof(long) * (p - ptnb));
78 el me /* le point existe deja */
79
80
81 ptTotNb--;
82
83
84 ptCribEptnb) = ptval;
85
86 printf("\n-----------------------------
87 /* --------------affichage des points du crible ----------------------
88 printf("POINTS DU CRIBLE (abscisses dans l'ordre croissant):\n\n"
89 'Rang des,\n"
90 'dizaines: );
91 for (p = 0; p < ptTotNb; p++)
92
93 if (p % 10 == 0)
94 printf("\n%7d V, p);
95 printf("%61d ", ptCrib[p));
96
97 printf("\n\n---------------------------
98 /* -------------- determiner les periodes du crible -------------------
99 memcpy(ptReste, ptCrib, sizeof(long) * ptTotNb);
100
101 for (p = 0; p < ptTotNb; p++)
102
103 if ( ptReste(p) == COUVERT
104 continue;
105 /* -----------calculer une periode commencant au point courant ---- *1
106 per. mod = 0;
107 do
108
109 per. mod++;
110 per-ini = (short) (ptCrib[p] % per.mod);
111 per.couv = 0;
112 for (ptnb = 0, ptval -per.ini;
113 ptnb < ptTotNb && ptval >= ptCrib[ptnb];
114 ptnb++)
115
118 if (ptval == ptCrib[ptnbl)
117
118 per. couv++;
119 ptval += per mod;
120
121
122 I
123 while (ptnb < ptTotNb);
124 1* -----------tester la redondance de la periode ------------------
125 for (ptnb = 0, ptval = per.ini, flag = REDONDANT;
128 ptnb < ptTotNb;
127 ptnb++)
128
129 if (ptval == ptCrib(ptnbj)
130
131 if (ptval == ptResteEptnbl)
132
133 ptResteEptnbJ = COUVERT;
134 flag = NON-REDONDANT;
135 I
138 ptval += per.mod;
137
138
139 if (flag == NON_REDONDANT)
140 perCrib[perTotNb++J = per;
141
142 /* -------------- calcul de la periode du crible ----------------------
143 percrib = perCr.ib(0J.mod;
144 for (p = 1; p < perTotNb; p++)
145
146 if ((long) perCrib(pJ.mod >= percrib)
147 percrib *= (long) perCrib[p).mod / Euclide((long)perCrib[p].mod, percrib);
148 else
 78 of NewMusic
Perspectives

CEMAMu
pr.c

Line# Source Line

149 percrib *= (long) perCribCp].mod / Euclide(percrib, (long)perCribp]. mod);

150 }
151 / ------ ----- affichage de la formule du crible -------------------/
152 printf("FORMULE DU CRIBLE:\n"
153 "dans chaque parenthese on a dans l\'ordre:\n"
154 "(module, point de depart, nombre de points couverts)\n\n");
155 printf(" L = ");
156 for (p = 0; p < perTotNb; p++)
157 {
158 if (p != 0)
159 {
160 if (p % 3 == 0)
161 printf("\n "
162 printf("+ ");
163 }
164 printf (" (%5d, %5d, %5d) ",perCrib p]. mod,perCrib p]. ini,perCrib[p] . couv);
165 }
166 printf("\n\n periode du crible: P = %lu\n", percrib);
167 }
168 /* ========================= algorithme d'Euclide ==================== */
169 unsigned long Euclide (al, a2) /* on suppose al >= a2 > 0 */
170 unsigned long al;
171 unsigned long a2;
172 {
173 unsigned long tmp;
174
175 while ((tmp = al % a2) != 0)
176 {
177 al = a2;
178 a2 = tmp;
179 }
180 return a2;
181 )