Category : BASIC Source Code
Archive   : UBAS830.ZIP
Filename : RATDEP.UB

7
˜ä See end of listing for a program description.
r§"decimals after point"ÁPÀPÑñ
݀܁Pæñ.ñ)
ŽŸ€àñÂñåP)À©P
Ê(DрÆñ æP)À™"Maximal dimension set to "ÁDÝñ


2¤„RD)„BDD)„MDD)„VD)˜È
used by main algorithm
]
<¤„XD)„YD)„ZD)˜
 used by *SEARCH
m
FƒPPÑð.ñ
¦
PƒPsÑñ˜\ Display width for printing coefficients
¯
Z˜
¾
dˆõMENUó
Ö
n¸ÿÿÀˆõCHOICEÓó¹t
ß
x˜
‚õMENU™"1: Input data to check for linear dependence"
bΪ"2: Input datum to test for algebraicity (previous value is x)"
€–™"3: Run form reduction"
¢ ™"4: Look for short vectors"
Ъ™"5: Change display width and redisplay"
Ù´˜†
¾õCHOICE§"CHOICE (0 for menu)"ÁƒAÀÄƒAÑð‡õMENU|
3ȍàƒAÑñ
‡õLINEAR
LҍùƒAÑñ‡õALGÀ
s܍ ƒDTÑðŽ™"No data."À‡õCHOICEu

æ:ƒAÑñ‡õINITÖ
ÍðƒAÑñŽoƒRDÑð™"First run reduction!"‡õSEARCHš
úƒAÑñŽ™"Width (Current is"ÁƒPsÁ")"ÁÀ§ƒPsÀ‡õHowbig?

‡õCHOICEg

)
˜
9
õLINEAR
h"
§"Number of entries (n=0 to return)"ÁM
Š,
€èMÔñMҁD}Ž•
Õ6
NсMÞñ
ÀƒRDÑðÀƒDTÑðÀ‰ƒIÑðŠNÀ™"X("ÁƒIÁ") ="ÁÀ§„RƒI)
ë@
„RƒI)ÑðŽ•
ýJ
ŒÀƒDTÑñ
À•
T
˜
/^
õALG§"Degree"ÁMÀÜMÔñ
Ž•
bh
NсMÀƒRDÑðÀƒDTÑðÀ§"X"ÁƒXÀƒXÑðŽ•
r
€ÀƒX)Òñ
Ž§"|X|<=1 is best. Invert X (0/1)"ÁƒI
Ç|
ÀtƒIŽƒXÑñ
æƒXÀ™"X inverted"
†
„Rð)Ññ
À‰ƒIÑðŠNÞñ
À„RƒIÝñ
)фRƒI)åƒXÀŒÀƒDTÑñ
À•

˜
)š
õINIT
o¤
™"Parameter (best <"Á€Üñ .ñåP)Á"; see comments. 0 exits)"Á
–®
§ƒRQÀ6ƒRQÑðŽ•ƒRQÑñ
ïƒRQ
Ÿ¸
˜L
­Â
ƒRrÑñ

ÇÌ
¨¢„MðÁNÂðÁN)
Ö
„Vð)р´„Rð))ïñ݀µ„Rð))ïñÀ„Vñ
)рµ„Rð)倳„Rñ
)))
Nà
‰ƒJÑñ
ŠNÀ„MƒJÂð)р´„Rð)倳„RƒJ)))æ„Vð)ÀŒ
Ӑ
A„Vñ
)ÑðŽ„Vñ
)Ññ
À™"Assuming real entries. "ÀƒRrÑðÀ¶
Øô
‰ƒJÑñŠNÀ„MƒJÂñ
)рµ„Rð)倳„RƒJ)))æ„Vñ
)ÀŒ
ÿþ
„Vñ
)фVñ
)ïñæ„Vð)åƒRQ
·À„Vð)фVð)åƒRQ
=‰ƒJÑñŠNÀ„VƒJ)Ññ
ÀŒ
y¨¢„BðÁNÂðÁN)À‰ƒIÑðŠNÀ„BƒIƒI)Ññ
ÀŒ
‚&˜/
˜0ƒKÑñ
À‡õR1&

:õR2ƒMфMƒKƒKÞñ
)ÀƒVфVƒK)݃MåƒMå„VƒKÞñ
)À„MƒKƒKÞñ
)уMå„VƒKÞñ
)æƒV
L D„VƒK)фVƒKÞñ
)å„VƒK)æƒVÀ„VƒKÞñ
)уV
z N¥¢„BƒKÂðÁN)¢„BƒKÞñ
ÂðÁN)
¼ XiƒKÒñ
Ž¥¢„MƒKÂðÃKÞñ)¢„MƒKÞñ
ÂðÃKÞñ)
Õ b‰ƒIуKÝñ
ŠN
V
lƒVфMƒIƒK)À„MƒIƒK)фMƒIƒKÞñ
)ރMåƒVÀ„MƒIƒKÞñ
)уV݄MƒKƒKÞñ
)å„MƒIƒK)ÀŒ
m
vƒKÒñ
Ž¡ƒK
Ž
€õR1ƒLуKÞñ
ÀˆõR3ÿò
à
Š„VƒK)æ„VƒKÞñ
)݄MƒKƒKÞñ
)å„MƒKƒKÞñ
)ԃPP‡õR2Q
”‰ƒLуKÞñŠð‹Þñ
ÀˆõR3ÿòŒƒL
'ž ƒKÀÔƒKՁN‡õR1&
q¨ƒRDÑñ
À‡õHOWBIG?˜ This is the exit line.
™²õR3F€À„MƒKƒL))Õð.ñŽ•
»¼ƒRрÜð.ñ݄MƒKƒL))
 ƉƒIÑðŠNÀ„BƒKƒI)фBƒKƒI)ރRå„BƒLƒI)ÀŒƒI
r ЄMƒKƒL)фMƒKƒL)ރRÀ‰ƒIÑðŠƒLÞñ
À„MƒKƒI)фMƒKƒI)ރRå„MƒLƒI)ÀŒ
y Ú•
‚ ä˜
Ê îõHOWBIG™" coefficients | value of linear comb. | value of form"


ø‰ƒIÑðŠNÀ¨ƒAFƒAÀ‰ƒJÑðŠNÀ™€ìƒPs)„BƒIƒJ)Á
e
ƒAуA݄BƒIƒJ)å„RƒJ)ÀƒAFуAF݄BƒIƒJ)å„BƒIƒJ)ÀŒÀ™"|"Á
~
ˆõPRgó(ƒA)À™"|"Á
Ë
ˆõPRgó(ƒAF݃RQå€ÀƒA)ïñބBƒIÂð)ïñރRrå„BƒIÂñ
)ïñ)À™
Ô
ŒÀ•
Ý
*˜
4õSEARCHƒKсNÀ¨„YN)„ZN)ƒNN
W>§"Search up to square length (try v(0) for shortest vector)"ÁƒTT
˜H§"Print vectors (0/1)"ÁSÀSŽ™"vector | len. | form"
¥R‡õS1
\õS0¡ƒKÀ„ZƒK)ÑðÀ‰ƒIуKÝñ
ŠNÀ„ZƒK)фZƒK)݄MƒIƒK)å„XƒI)ÀŒ
Rf„YƒK)фYƒKÝñ
)݄VƒKÝñ
)å(„XƒKÝñ
)݄ZƒKÝñ
))ïñ
’põS1„XƒK)р܀Å(ƒTTބYƒK))æ„VƒK))ބZƒK))
èzõS2•„VƒK)å(„XƒK)݄ZƒK))ïñ҃TTބYƒK)À ƒKÀ¡„XƒK)À‘L
„˜Æif K=N%+1 then print "ERROR":stop:return
-ŽÚƒK‡õS0^
{˜0€èõ„Xð)„Yð)}Þñ
Ž™ñåƒNNÁ"nonzero vectors up to"Á€ìÂñ)ƒTT
Ģ˥
Û¬SŽƒAFÑðÀ‰ƒIÑðŠNÀƒAÑðÀ‰ƒJÑðŠNÀƒAуA݄XƒJ)å„BƒJƒI)
¶ÀŒÀ™€ìƒPs)ƒAÁÀƒAFуAF݃Aå„RƒI)
'ÀÀŒÀ™"|"ÁÀˆõPRgó(ƒAF)
`ÊÀ™"|"ÁÀˆõPRgó(„Vð)å(„Xð)݄Zð))ïñ݄Yð))À™
~Ô ƒNNÀ¡„XƒK)À‡õS2K
‡Þ˜
™èõPR(ƒPR)
¤òºƒPE
¾üƒPEÑðÀkƒPRÑðŽ¶
òŸ€ÀƒPR)Óñ
ÀƒPRуPRæñ
ÀƒPEуPEÝñ
À‘r
&Ó€ÀƒPR)Ôñ
ÀƒPRуPRåñ
ÀƒPEуPEÞñ
À‘¦
P·À™€ìñÂñ)ƒPRÁ" E"Á€ìñ)ƒPEÁ
W$•
`.˜
ª8˜ This program uses the reduction algorithm of Lengstra, Lengstra,
öB˜ Lovasz (Math. Ann. 261 (1982) 515-534) to obtain a "reduced basis"
BL˜ for the following bilinear form over Z, (N is a large parameter):
KV˜
“`˜ q(a0, ... ,an) = a2^2+a3^2+...+an^2+N*abs(z0*a0+...+zn*an)^2
œj˜
æt˜ This tests integral dependence of the complex numbers z0,...,zn,
3~˜ since a short vector for the form makes z0*a0+...+zn*an very small.
}ˆ˜ To test if a number z is algebraic, zi=z^i is used in the above.
†’˜
Ìœ˜ If z0/z1 is real the program assumes the zi are ALL real and
ü¦˜ uses the following form Q instead of q
°˜
Eº˜ Q(a0, ... ,an) = a1^2+...+an^2+N*(z0*a0+...+zn*an)^2
NĘ
šÎ˜ A search algorithm is included to find short vectors for the form.
£Ø˜
â☠The program prompts for a parameter RQ. N is 10^RQ.
ëì˜
8ö˜ Suggested values (assuming the zi are not too far from 1): To find
€˜ ai bounded by 10^c you will need a bit more than n*c digits of
Ë
˜ accuracy for the zi. Try RQ around n*c (2*n*c in the real case),
˜ but below 2*(number of digits carried) to limit roundoff error.
˜
j(˜ Running time is roughly proportional to RQ*(n-1)^2 for given POINT.
¬2˜ Thus, with POINT and RQ optimized for for given c and n,
á<˜ it is very roughly proportional to c^3*n^5.
.F˜ W.D. Neumann