Project

General

Profile

Feature #951

New function: IsSqFree

Added by Anna Maria Bigatti over 7 years ago. Updated over 7 years ago.

Status:
Closed
Priority:
Normal
Assignee:
John Abbott
Category:
New Function
Target version:
CoCoALib-0.99550 spring 2017
Start date:
24 Oct 2016
Due date:
% Done:

100%

Estimated time:
11.10 h
Spent time:
11.30 h

Description

Write function IsSquareFree (or IsSqFr, or IsSqFree) for a RingElem

Related issues

Related to CoCoALib - Feature #796: CoCoALib function for radical (or SqFree) of a polynomialClosed2015-11-05

Related to CoCoALib - Slug #952: GCD very slowClosed2016-10-25

Related to CoCoALib - Support #953: new file for old functions: obsolescent.CClosed2016-10-26

History

#1 Updated by Anna Maria Bigatti over 7 years ago

  • Subject changed from IsSquareFree to New function: IsSquareFree

Currently there is a function called IsRadical(PP) for a PPMonoidElem.
Should it be called IsSquareFree?

"A number is said to be squarefree (or sometimes quadratfrei; Shanks 1993) if its prime decomposition contains no repeated factors."
"The radical of any integer n, rad(n), is the largest square-free divisor of n"

This notation seems well-established in Number Theory, and it does make sense... (even though it is not what I'm used to)

#2 Updated by Anna Maria Bigatti over 7 years ago

  • Related to Feature #796: CoCoALib function for radical (or SqFree) of a polynomial added

#3 Updated by John Abbott over 7 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 10

A function which tests whether a value is square-free is probably going to be quite similar to a function which determines a factorization. It would be nice to have a way to avoid duplicating the code for computing the factorization, but I do not currentlky see how to do this (without making a mess).

Probably the simplest (and quickest?) approach is just to duplicate the code, modify it so it simply says yes/no; then perhaps at the end see whether it makes sense to remerge it with the factorization code.

Regarding names: in the file factor.H there is a function called SqFreeFactor, so to be consistent the test should be called IsSqFree (or we change the name of SqFreeFactor).

#4 Updated by John Abbott over 7 years ago

  • Status changed from In Progress to Feedback
  • Assignee set to John Abbott
  • % Done changed from 10 to 90

I have checked in code for the new fn IsSqFree (incl. tests and doc).

It is not complete:
  • currently gives error for polys with coeffs in ZZ (because it wants coeffs in a field)
  • for integers with large prime factors it cannot decide (in CoCoALib return value is *bool3)

NOTE the special fn for PPs is still called IsRadical; should we rename it?

#5 Updated by John Abbott over 7 years ago

#6 Updated by Anna Maria Bigatti over 7 years ago

While comparing various implementations of radical(0-dim) I found this, unexpected for me:
IsSqFree is quite fast on this example (not square-free) if poly ring is multivariate (ZZ/(101)[z,w]). If univariate, doesn't seem to terminate:

use ZZ/(101)[z];
MP := z^501 +43*z^499 +35*z^498 -25*z^497 +7*z^496 +31*z^495 -25*z^494 -11*z^493 -12*z^492 -39*z^491 -48*z^490 -35*z^489 -34*z^488 +15*z^487 +50*z^486 -23*z^485 -43*z^484 -24*z^483 +30*z^482 +22*z^481 -37*z^480 -12*z^479 +27*z^478 +27*z^477 +49*z^476 +29*z^475 +30*z^474 +17*z^473 -3*z^472 -42*z^471 +41*z^470 -10*z^469 +13*z^468 +7*z^466 -8*z^465 -37*z^464 +27*z^463 -43*z^462 +48*z^461 -46*z^460 -23*z^459 -10*z^458 +19*z^457 +5*z^456 -14*z^455 -45*z^454 +38*z^453 +26*z^452 +47*z^451 -30*z^450 +47*z^449 +29*z^448 +43*z^447 +32*z^446 -44*z^445 +34*z^444 -36*z^443 +36*z^442 -44*z^441 -36*z^440 -45*z^439 +13*z^438 +13*z^437 -23*z^436 -33*z^435 -4*z^434 -z^433 +50*z^432 +23*z^431 -43*z^430 -37*z^429 -2*z^428 +25*z^427 -29*z^426 -21*z^425 +18*z^424 +49*z^423 -14*z^422 +14*z^421 +15*z^420 -7*z^419 +12*z^418 -45*z^417 -14*z^416 -32*z^415 -23*z^414 +22*z^413 +6*z^412 -37*z^411 -12*z^410 +3*z^409 -23*z^408 +36*z^407 +17*z^406 -16*z^405 +43*z^404 +23*z^403 -30*z^402 +49*z^401 -11*z^400 +21*z^399 -45*z^398 -14*z^397 -4*z^396 +22*z^395 -6*z^394 -47*z^393 +8*z^392 +11*z^391 +24*z^390 -15*z^389 +46*z^388 -17*z^387 +17*z^386 -47*z^385 +48*z^384 -43*z^383 +48*z^382 -47*z^381 -46*z^380 +42*z^379 +33*z^378 -35*z^377 -34*z^376 +33*z^375 +6*z^374 -18*z^373 -14*z^372 -35*z^371 -36*z^370 -31*z^369 -25*z^368 -7*z^367 +49*z^366 -6*z^365 +47*z^364 -27*z^363 +42*z^362 -4*z^361 +14*z^360 +25*z^359 +26*z^358 +46*z^357 +35*z^356 +15*z^355 +17*z^354 -5*z^353 -10*z^352 +27*z^351 +15*z^350 +6*z^349 +28*z^348 -33*z^347 +14*z^346 -25*z^344 -4*z^343 -23*z^342 +18*z^341 +6*z^340 -49*z^339 -4*z^338 +44*z^337 +27*z^336 +19*z^335 -38*z^334 -31*z^333 +15*z^332 -28*z^331 +41*z^330 +46*z^329 -34*z^328 -8*z^327 -49*z^326 -4*z^325 +10*z^324 +16*z^323 -37*z^322 +50*z^321 +28*z^320 +9*z^319 -23*z^318 +50*z^317 +14*z^316 -42*z^315 +17*z^314 -43*z^313 -30*z^312 +20*z^311 +40*z^309 -25*z^308 +3*z^307 +12*z^306 +31*z^305 +47*z^304 +44*z^303 -21*z^302 -6*z^301 -39*z^300 +45*z^299 +47*z^298 -49*z^297 -27*z^296 +5*z^295 +38*z^294 +35*z^293 +24*z^292 -37*z^291 -2*z^290 +38*z^289 -40*z^288 +32*z^287 +32*z^286 -22*z^285 -8*z^284 +11*z^283 -45*z^282 -28*z^281 +9*z^280 +22*z^279 +32*z^278 -11*z^277 +50*z^276 -17*z^275 +50*z^274 -17*z^273 -26*z^272 -30*z^271 -3*z^270 -3*z^269 +43*z^268 +13*z^267 +z^266 -41*z^265 +14*z^264 +32*z^263 +43*z^262 -z^261 +41*z^260 -z^259 -8*z^258 +10*z^257 +39*z^256 +15*z^255 +4*z^254 -11*z^253 +22*z^252 -38*z^251 +43*z^250 -34*z^249 +35*z^248 -37*z^247 -28*z^246 +19*z^245 +7*z^244 -39*z^243 -15*z^242 -18*z^241 -27*z^240 +19*z^239 +24*z^238 +37*z^237 -21*z^236 -22*z^235 +30*z^234 -28*z^233 -26*z^232 -26*z^231 +36*z^230 -43*z^229 -13*z^228 +15*z^227 +43*z^226 +28*z^225 +19*z^224 +28*z^223 -40*z^222 +30*z^221 -12*z^220 -41*z^219 -z^218 -6*z^217 -11*z^216 +14*z^215 -43*z^214 -46*z^213 +23*z^212 +37*z^211 -45*z^210 +3*z^209 +46*z^208 -7*z^207 +37*z^206 +34*z^205 +17*z^204 +10*z^203 +35*z^202 -13*z^201 -25*z^200 +19*z^199 +32*z^198 -z^197 -37*z^196 +16*z^195 -28*z^194 +7*z^193 +16*z^192 +14*z^191 +34*z^190 -21*z^189 +22*z^188 -50*z^187 +38*z^186 -14*z^185 +23*z^184 +z^183 -10*z^182 +42*z^181 -13*z^180 -31*z^179 -33*z^178 +41*z^177 +4*z^176 -42*z^175 +21*z^174 +22*z^173 -9*z^172 -39*z^171 +10*z^170 -33*z^169 -33*z^168 +6*z^167 -20*z^166 -50*z^165 -29*z^164 +34*z^163 -47*z^162 -12*z^161 +z^160 -24*z^159 +23*z^158 +15*z^157 -30*z^156 +43*z^155 +16*z^154 -32*z^153 -48*z^152 +31*z^151 -45*z^150 +28*z^149 +4*z^148 +2*z^147 +49*z^146 +29*z^145 -23*z^144 -17*z^143 -45*z^142 +19*z^141 +46*z^140 +6*z^139 +37*z^138 +23*z^137 +23*z^136 -24*z^135 -z^134 +5*z^133 +39*z^132 +25*z^131 +48*z^130 -31*z^129 -2*z^128 -4*z^127 +33*z^126 +43*z^125 +33*z^124 +6*z^123 +13*z^122 +43*z^121 +12*z^120 +9*z^119 -20*z^118 +z^117 +2*z^116 +5*z^115 -17*z^114 -z^113 -14*z^112 -19*z^111 -26*z^110 +23*z^109 -28*z^108 -36*z^107 +10*z^106 -47*z^105 +16*z^104 -19*z^103 -20*z^102 +20*z^101 -39*z^100 +45*z^99 +42*z^98 +15*z^97 -36*z^96 +40*z^95 -11*z^94 -24*z^93 -21*z^92 -8*z^91 +38*z^90 -44*z^89 -50*z^88 +13*z^87 +12*z^86 +37*z^85 +46*z^84 +37*z^83 -45*z^82 +35*z^81 -3*z^80 +39*z^79 -12*z^78 +45*z^77 +10*z^76 -22*z^75 -25*z^74 +20*z^73 -2*z^72 +18*z^71 +34*z^70 +41*z^69 -38*z^68 +19*z^67 -49*z^66 -48*z^65 +47*z^64 -20*z^63 -31*z^62 -8*z^61 -7*z^60 -4*z^59 -19*z^58 -18*z^57 +28*z^56 +9*z^55 +49*z^54 -13*z^53 +21*z^52 -14*z^51 +8*z^50 +22*z^49 -9*z^48 -18*z^47 -43*z^46 +48*z^45 -11*z^44 +21*z^43 +45*z^42 +20*z^41 -10*z^40 +37*z^39 -49*z^38 +5*z^37 -23*z^36 +38*z^35 -13*z^34 +12*z^33 +32*z^32 -44*z^31 +19*z^30 -25*z^29 -21*z^28 -36*z^27 -47*z^26 +19*z^25 +17*z^24 -30*z^23 +34*z^22 +43*z^21 +5*z^20 +3*z^19 +15*z^18 -36*z^17 +28*z^16 -49*z^15 +23*z^14 -32*z^13 -10*z^12 -50*z^11 -29*z^10 +30*z^9 -30*z^8 +5*z^7 +34*z^6 +44*z^5 -50*z^4 -44*z^3 +44*z^2;
IsSqFree(MP);

#7 Updated by Anna Maria Bigatti over 7 years ago

Reducing the example. These give segv:

Use ZZ/(101)[z];
MP :=  -19*z^111 -26*z^110 +23*z^109 -28*z^108 -36*z^107 +10*z^106 -47*z^105 +16*z^104 -19*z^103 -20*z^102 +20*z^101 -39*z^100 +45*z^99 +42*z^98 +15*z^97 -36*z^96 +40*z^95 -11*z^94 -24*z^93 -21*z^92 -8*z^91 +38*z^90 -44*z^89 -50*z^88 +13*z^87 +12*z^86 +37*z^85 +46*z^84 +37*z^83 -45*z^82 +35*z^81 -3*z^80 +39*z^79 -12*z^78 +45*z^77 +10*z^76 -22*z^75 -25*z^74 +20*z^73 -2*z^72 +18*z^71 +34*z^70 +41*z^69 -38*z^68 +19*z^67 -49*z^66 -48*z^65 +47*z^64 -20*z^63 -31*z^62 -8*z^61 -7*z^60 -4*z^59 -19*z^58 -18*z^57 +28*z^56 +9*z^55 +49*z^54 -13*z^53 +21*z^52 -14*z^51 +8*z^50 +22*z^49 -9*z^48 -18*z^47 -43*z^46 +48*z^45 -11*z^44 +21*z^43 +45*z^42 +20*z^41 -10*z^40 +37*z^39 -49*z^38 +5*z^37 -23*z^36 +38*z^35 -13*z^34 +12*z^33 +32*z^32 -44*z^31 +19*z^30 -25*z^29 -21*z^28 -36*z^27 -47*z^26 +19*z^25 +17*z^24 -30*z^23 +34*z^22 +43*z^21 +5*z^20 +3*z^19 +15*z^18 -36*z^17 +28*z^16 -49*z^15 +23*z^14 -32*z^13 -10*z^12 -50*z^11 -29*z^10 +30*z^9 -30*z^8 +5*z^7 +34*z^6 +44*z^5 -50*z^4 -44*z^3 +44*z^2;
IsSqFree(monic(MP));

Use ZZ/(101)[z];
MP :=   -23*z^408 +36*z^407 +17*z^406 -16*z^405 +43*z^404 +23*z^403 -30*z^402 +49*z^401 -11*z^400 +21*z^399 -45*z^398 -14*z^397 -4*z^396 +22*z^395 -6*z^394 -47*z^393 +8*z^392 +11*z^391 +24*z^390 -15*z^389 +46*z^388 -17*z^387 +17*z^386 -47*z^385 +48*z^384 -43*z^383 +48*z^382 -47*z^381 -46*z^380 +42*z^379 +33*z^378 -35*z^377 -34*z^376 +33*z^375 +6*z^374 -18*z^373 -14*z^372 -35*z^371 -36*z^370 -31*z^369 -25*z^368 -7*z^367 +49*z^366 -6*z^365 +47*z^364 -27*z^363 +42*z^362 -4*z^361 +14*z^360 +25*z^359 +26*z^358 +46*z^357 +35*z^356 +15*z^355 +17*z^354 -5*z^353 -10*z^352 +27*z^351 +15*z^350 +6*z^349 +28*z^348 -33*z^347 +14*z^346 -25*z^344 -4*z^343 -23*z^342 +18*z^341 +6*z^340 -49*z^339 -4*z^338 +44*z^337 +27*z^336 +19*z^335 -38*z^334 -31*z^333 +15*z^332 -28*z^331 +41*z^330 +46*z^329 -34*z^328 -8*z^327 -49*z^326 -4*z^325 +10*z^324 +16*z^323 -37*z^322 +50*z^321 +28*z^320 +9*z^319 -23*z^318 +50*z^317 +14*z^316 -42*z^315 +17*z^314 -43*z^313 -30*z^312 +20*z^311 +40*z^309 -25*z^308 +3*z^307 +12*z^306 +31*z^305 +47*z^304 +44*z^303 -21*z^302 -6*z^301 -39*z^300 +45*z^299 +47*z^298 -49*z^297 -27*z^296 +5*z^295 +38*z^294 +35*z^293 +24*z^292 -37*z^291 -2*z^290 +38*z^289 -40*z^288 +32*z^287 +32*z^286 -22*z^285 -8*z^284 +11*z^283 -45*z^282 -28*z^281 +9*z^280 +22*z^279 +32*z^278 -11*z^277 +50*z^276 -17*z^275 +50*z^274 -17*z^273 -26*z^272 -30*z^271 -3*z^270 -3*z^269 +43*z^268 +13*z^267 +z^266 -41*z^265 +14*z^264 +32*z^263 +43*z^262 -z^261 +41*z^260 -z^259 -8*z^258 +10*z^257 +39*z^256 +15*z^255 +4*z^254 -11*z^253 +22*z^252 -38*z^251 +43*z^250 -34*z^249 +35*z^248 -37*z^247 -28*z^246 +19*z^245 +7*z^244 -39*z^243 -15*z^242 -18*z^241 -27*z^240 +19*z^239 +24*z^238 +37*z^237 -21*z^236 -22*z^235 +30*z^234 -28*z^233 -26*z^232 -26*z^231 +36*z^230 -43*z^229 -13*z^228 +15*z^227 +43*z^226 +28*z^225 +19*z^224 +28*z^223 -40*z^222 +30*z^221 -12*z^220 -41*z^219 -z^218 -6*z^217 -11*z^216 +14*z^215 -43*z^214 -46*z^213 +23*z^212 +37*z^211 -45*z^210 +3*z^209 +46*z^208 -7*z^207 +37*z^206 +34*z^205 +17*z^204 +10*z^203 +35*z^202 -13*z^201 -25*z^200 +19*z^199 +32*z^198 -z^197 -37*z^196 +16*z^195 -28*z^194 +7*z^193 +16*z^192 +14*z^191 +34*z^190 -21*z^189 +22*z^188 -50*z^187 +38*z^186 -14*z^185 +23*z^184 +z^183 -10*z^182 +42*z^181 -13*z^180 -31*z^179 -33*z^178 +41*z^177 +4*z^176 -42*z^175 +21*z^174 +22*z^173 -9*z^172 -39*z^171 +10*z^170 -33*z^169 -33*z^168 +6*z^167 -20*z^166 -50*z^165 -29*z^164 +34*z^163 -47*z^162 -12*z^161 +z^160 -24*z^159 +23*z^158 +15*z^157 -30*z^156 +43*z^155 +16*z^154 -32*z^153 -48*z^152 +31*z^151 -45*z^150 +28*z^149 +4*z^148 +2*z^147 +49*z^146 +29*z^145 -23*z^144 -17*z^143 -45*z^142 +19*z^141 +46*z^140 +6*z^139 +37*z^138 +23*z^137 +23*z^136 -24*z^135 -z^134 +5*z^133 +39*z^132 +25*z^131 +48*z^130 -31*z^129 -2*z^128 -4*z^127 +33*z^126 +43*z^125 +33*z^124 +6*z^123 +13*z^122 +43*z^121 +12*z^120 +9*z^119 -20*z^118 +z^117 +2*z^116 +5*z^115 -17*z^114 -z^113 -14*z^112 -19*z^111 -26*z^110 +23*z^109 -28*z^108 -36*z^107 +10*z^106 -47*z^105 +16*z^104 -19*z^103 -20*z^102 +20*z^101 -39*z^100 +45*z^99 +42*z^98 +15*z^97 -36*z^96 +40*z^95 -11*z^94 -24*z^93 -21*z^92 -8*z^91 +38*z^90 -44*z^89 -50*z^88 +13*z^87 +12*z^86 +37*z^85 +46*z^84 +37*z^83 -45*z^82 +35*z^81 -3*z^80 +39*z^79 -12*z^78 +45*z^77 +10*z^76 -22*z^75 -25*z^74 +20*z^73 -2*z^72 +18*z^71 +34*z^70 +41*z^69 -38*z^68 +19*z^67 -49*z^66 -48*z^65 +47*z^64 -20*z^63 -31*z^62 -8*z^61 -7*z^60 -4*z^59 -19*z^58 -18*z^57 +28*z^56 +9*z^55 +49*z^54 -13*z^53 +21*z^52 -14*z^51 +8*z^50 +22*z^49 -9*z^48 -18*z^47 -43*z^46 +48*z^45 -11*z^44 +21*z^43 +45*z^42 +20*z^41 -10*z^40 +37*z^39 -49*z^38 +5*z^37 -23*z^36 +38*z^35 -13*z^34 +12*z^33 +32*z^32 -44*z^31 +19*z^30 -25*z^29 -21*z^28 -36*z^27 -47*z^26 +19*z^25 +17*z^24 -30*z^23 +34*z^22 +43*z^21 +5*z^20 +3*z^19 +15*z^18 -36*z^17 +28*z^16 -49*z^15 +23*z^14 -32*z^13 -10*z^12 -50*z^11 -29*z^10 +30*z^9 -30*z^8 +5*z^7 +34*z^6 +44*z^5 -50*z^4 -44*z^3 +44*z^2;
IsSqFree(monic(MP));

#8 Updated by John Abbott over 7 years ago

I believe I have fixed the SEGV bug. Checked in new version of DUPFp.C. @Anna: could you check? :-)

NOTE problem was calling SmallFpImpl::myExport instead of SmallFpImpl::myExportNonNeg

#9 Updated by Anna Maria Bigatti over 7 years ago

John Abbott wrote:

I believe I have fixed the SEGV bug. Checked in new version of DUPFp.C. @Anna: could you check? :-)

Perfect, and faster than the multivariate case :-)

#10 Updated by Anna Maria Bigatti over 7 years ago

John Abbott wrote:

NOTE the special fn for PPs is still called IsRadical; should we rename it?

yes, please (and make it obsolescent? ;-)

#11 Updated by Anna Maria Bigatti over 7 years ago

  • Related to Support #953: new file for old functions: obsolescent.C added

#12 Updated by John Abbott over 7 years ago

I have renamed IsRadical (for PPMonoidElem)to IsSqFree. The old fn has been moved to obsolescent.C (see #953).
I'll check documentation -- OK, updated and checked in.

#13 Updated by Anna Maria Bigatti over 7 years ago

  • Subject changed from New function: IsSquareFree to New function: IsSqFree

Renamed AreGensSquareFreeMonomial into AreGensSqFreeMonomial.
Added to CoCoA-5 (with doc) and to obsolescent.C (and to test).

#14 Updated by John Abbott over 7 years ago

  • Status changed from Feedback to Closed
  • % Done changed from 90 to 100
  • Estimated time set to 11.10 h

Also available in: Atom PDF