From 855e0f3c623f412edebef2e6837657eaeff6d713 Mon Sep 17 00:00:00 2001 From: Cedric Bastoul Date: Wed, 9 Nov 2005 23:58:41 +0100 Subject: [PATCH] piplib 1.3.4 --- Makefile.in => autoconf/Makefile.in | 7 +- configure.in => autoconf/configure.in | 141 ++-- doc/pip.ps | 1092 ++++++++++++++-------------- doc/source/images/negatifs.eps | 110 +++ doc/source/images/negatifs.fig | 26 + doc/source/makefile | 23 + doc/source/pip.bbl | 22 + doc/source/pip.tex | 1257 +++++++++++++++++++++++++++++++++ example/Makefile | 4 +- example/sor1d.pip | 28 + include/piplib/funcall.h | 4 +- include/piplib/piplib.h | 8 +- include/piplib/type.h | 5 + source/maind.c | 40 +- source/piplib.c | 56 +- source/sol.c | 8 +- source/tab.c | 31 +- source/traiter.c | 4 +- test/makefile | 2 +- 19 files changed, 2236 insertions(+), 632 deletions(-) rename Makefile.in => autoconf/Makefile.in (98%) rename configure.in => autoconf/configure.in (69%) create mode 100644 doc/source/images/negatifs.eps create mode 100644 doc/source/images/negatifs.fig create mode 100644 doc/source/makefile create mode 100644 doc/source/pip.bbl create mode 100644 doc/source/pip.tex create mode 100644 example/sor1d.pip diff --git a/Makefile.in b/autoconf/Makefile.in similarity index 98% rename from Makefile.in rename to autoconf/Makefile.in index 863a1d3..ad88b71 100644 --- a/Makefile.in +++ b/autoconf/Makefile.in @@ -9,7 +9,7 @@ # # makefile.in (or makefile if generated) of PIP/PipLib. makefile.in is not a # makefile, you must run the 'configure' shellscript to generate the makefile -# thanks to this file. +# thanks to this file. #/***************************************************************************** @@ -86,8 +86,8 @@ PIPLIB_INS_INC = $(prefix)/include INCFLAGS = -I $(PIPLIB_INC) $(EXTRA_INC) -LDFLAGS = $(EXTRA_LIBS) -CFLAGS = -c $(INCFLAGS) -fomit-frame-pointer -O2 $(EXTRA_FLAGS) $(DFLAGS) +LDFLAGS = $(EXTRA_LIBS) +CFLAGS = -c $(INCFLAGS) -fomit-frame-pointer -O2 $(EXTRA_FLAGS) $(DFLAGS) -fpic #/***************************************************************************** @@ -183,6 +183,7 @@ distclean: clean @echo " * DISTCLEANING PIP/PipLib *" @echo " *-----------------------------------------------*/" $(RM) -f config.cache config.log config.status Makefile + $(RM) -rf autom4te.cache install:: $(TO_BUILD:%=%install) diff --git a/configure.in b/autoconf/configure.in similarity index 69% rename from configure.in rename to autoconf/configure.in index 2b117c1..d5109e2 100644 --- a/configure.in +++ b/autoconf/configure.in @@ -8,11 +8,16 @@ dnl ** First version: august 11th 2001 ** dnl **-------------------------------------------------------------------**/ dnl dnl Input file for autoconf to build a configuration shellscript. +dnl To build the configure script from the PipLib's top-level directory, use +dnl autoconf -l autoconf autoconf/configure.in > configure +dnl if it doesn't work (invalid option -l) try -I instead +dnl autoconf -I autoconf autoconf/configure.in > configure AC_PREREQ(2.13) -AC_INIT(./source/piplib.c) -VERSION="1.3.3" +AC_INIT(source/piplib.c) +AC_CONFIG_AUX_DIR(autoconf) +VERSION="1.3.4" TO_BUILD_32="32" TO_BUILD_64="64" @@ -24,6 +29,8 @@ dnl **************************************************************************/ dnl Checks for typedefs, structures, and compiler characteristics. +dnl Sylvain Girbal suggested to put this into comment to better fit any +dnl architecture (and particularly Itanium -bah-). AC_CANONICAL_SYSTEM dnl Checks for programs. @@ -69,6 +76,35 @@ case "$target" in esac +dnl Test whether we are using SUN's ld rather than Solaris ld +dnl If so, we need to add -G -Bdynamic to the linking options +dnl This is a hack to avoid having to hack the piplib makefiles +dnl and configure scripts. (by Allen Leung) + +SOLARIS_LD=no +case $target_os in + solaris*) + case `which ld` in + /usr/ccs/bin/ld|/usr/ucb/ld) + SOLARIS_LD=yes + ;; + *) + ld -shared 2>&1 | grep 'fatal: option -h' + if test "$?" = "0"; then + SOLARIS_LD=yes + fi + ;; + esac + ;; + *) + ;; +esac +SOLARIS_LDFLAGS='' +if test "$SOLARIS_LD" = "yes"; then + SOLARIS_LDFLAGS='-G -Bdynamic' +fi + + dnl Checks sizeof the two supported cases. AC_CHECK_SIZEOF(int,1) AC_CHECK_SIZEOF(long long int,1) @@ -92,6 +128,14 @@ NEED_MP="no" GMP_INC="/usr/local/include" GMP_LIB="/usr/local/lib" + +dnl Some default values cause I'm not sure whether autoconf set them, while +dnl documentation says it does... +gmp_package="yes" +gmp_include_package="yes" +gmp_library_package="yes" + + dnl Options. dnl --with-pip=yes, --with-pip=no ou --without-pip dnl --with-lib=yes, --with-lib=no ou --without-lib @@ -136,30 +180,24 @@ AC_ARG_WITH(gmp_library, AC_ARG_ENABLE(int-version, [ --enable-int-version Only 'int' version is built], [ echo "Package int : $enableval" && - if test "$enableval"="no" ; then - TO_BUILD_32="32" - TO_BUILD_64="" - TO_BUILD_MP="" - fi ]) + TO_BUILD_32="32" && + TO_BUILD_64="" && + TO_BUILD_MP=""]) AC_ARG_ENABLE(llint-version, [ --enable-llint-version Only 'long long int' version is built], [ echo "Package long long int : $enableval" && - if test "$enableval"="no" ; then - TO_BUILD_32="" - TO_BUILD_64="64" - TO_BUILD_MP="" - fi ]) + TO_BUILD_32="" && + TO_BUILD_64="64" && + TO_BUILD_MP=""]) AC_ARG_ENABLE(mp-version, [ --enable-mp-version Only 'MP' version is built], [ echo "Package mp : $enableval" && - if test "$enableval"="no" ; then - TO_BUILD_32="" - TO_BUILD_64="" - TO_BUILD_MP="MP" - NEED_MP="yes" - fi ]) + TO_BUILD_32="" && + TO_BUILD_64="" && + TO_BUILD_MP="MP" && + NEED_MP="yes"]) dnl Packages to build. PACKAGES="$PIPLIB $PIP" @@ -174,15 +212,17 @@ dnl **************************************************************************/ dnl Checking for gmp AC_MSG_CHECKING(whether gmp works) if test "$gmp_package" = "no"; then + echo "GMP package not defined" AC_MSG_RESULT(no) TO_BUILD_MP="" else if test "$NEED_MP" = "no"; then echo "Mode normal GMP" + TO_BUILD="$TO_BUILD MP" AC_CHECK_HEADER(gmp.h, [AC_CHECK_LIB(gmp, __gmpz_init, - [EXTRA_LIBS="-lgmp $EXTRA_LIBS"], + [EXTRA_LIBS="$EXTRA_LIBS -lgmp"], [echo "Can't find gmp library." && echo "MP version will not be builded." && TO_BUILD_MP=""])], @@ -190,35 +230,38 @@ else echo "MP version will not be builded." && TO_BUILD_MP=""]) else - if test "$gmp_package" = "yes" ; then - AC_CHECK_HEADER(gmp.h, - [], - [AC_MSG_ERROR(Can't find gmp headers.)]) - AC_CHECK_LIB(gmp, - __gmpz_init, - [EXTRA_LIBS="-lgmp $EXTRA_LIBS"], - [AC_MSG_ERROR(Can't find gmp library.)]) - else - if test ! -d "$GMP_INC" ; then - AC_MSG_ERROR(Directory given for gmp include does not exist.) - fi - if test ! -d "$GMP_LIB" ; then - AC_MSG_ERROR(Directory given for gmp library does not exist.) - fi - - if test ! -f $GMP_INC/gmp.h; then - AC_MSG_ERROR(Can't find $GMP_INC/gmp.h) - else - if test -f $GMP_LIB/libgmp.so -o -f $GMP_LIB/libgmp.a ; then - EXTRA_INC="-I$GMP_INC" - EXTRA_LIBS="-L$GMP_LIB -lgmp $EXTRA_LIBS" - TO_BUILD="$TO_BUILD MP" - AC_MSG_RESULT(yes) - else - AC_MSG_ERROR(Can't find $GMP_LIB/libgmp{.so or .a}) - fi - fi + dnl Default given by --with-X is "yes", --without-X is "no". + if test "$gmp_package" != "yes" ; then + echo "(GMP path has been set by user)" + GMP_DIR=$gmp_package + GMP_LIB=$GMP_DIR/lib + GMP_INC=$GMP_DIR/include + EXTRA_INC="-I$GMP_INC" + EXTRA_LIBS="$EXTRA_LIBS -L$GMP_LIB" + dnl Useful for AC_CHECK_X to find what we want. + CPPFLAGS="-I$GMP_DIR/include $CPPFLAGS" + LDFLAGS="-L$GMP_DIR/lib $LDFLAGS" fi + + if test "$gmp_include_package" != "yes" ; then + CPPFLAGS="-I$GMP_DIR/include $CPPFLAGS" + EXTRA_INC="-I$GMP_INC" + fi + + if test "$gmp_library_package" != "yes" ; then + EXTRA_LIBS="$EXTRA_LIBS -L$GMP_LIB" + LDFLAGS="-L$GMP_DIR/lib $LDFLAGS" + fi + + AC_CHECK_HEADER(gmp.h, + [], + [AC_MSG_ERROR(Can't find gmp headers.)]) + AC_CHECK_LIB(gmp, + __gmpz_init, + [EXTRA_LIBS="$EXTRA_LIBS -lgmp"], + [AC_MSG_ERROR(Can't find gmp library.)]) + + AC_MSG_RESULT(yes) fi fi @@ -263,8 +306,8 @@ AC_SUBST(INSTALL) AC_SUBST(PACKAGES) AC_SUBST(TO_INSTALL) -dnl Makefile creation. -AC_OUTPUT(Makefile) +dnl Makefile creation (Allen Leung's fix). +AC_OUTPUT(Makefile:autoconf/Makefile.in) echo " /*-----------------------------------------------*" diff --git a/doc/pip.ps b/doc/pip.ps index 6949097..a6a77a1 100644 --- a/doc/pip.ps +++ b/doc/pip.ps @@ -10,7 +10,7 @@ %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -o pip.ps pip.dvi %DVIPSParameters: dpi=600, compressed -%DVIPSSource: TeX output 2004.04.14:2134 +%DVIPSSource: TeX output 2005.11.09:0103 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S @@ -1068,270 +1068,274 @@ E2A1732B3627109EA446CB320EBBE2E78281CDF0890E2E72B6711335857F1E23 0E73843FC6619DE017C8473A6D1B2BE5142DEBA285B98FA1CC5E64D2ADB981E6 472971848451A245DDF6AA3B8225E9AC8E4630B0FF32D679EC27ACAD85C6394E A6F71023B660EE883D8B676837E9EBA4E42BA8F365433A900F1DC3A9F0E88A26 -331A1063F97A958B9066B51C7EEE1181DAAD5462A0E9DB18E95B9B0BD6F297DC -A7146518B7610B50D1C64E7D9CD281CC8072C5F9D8C31C4036D66AD8417752ED -5802D244E4023488D62A7004F82D4A8FAFA7E902E7675BB07DA792813812F2DE -3E24045ACEA8B7177C995E89B48B150FD98E6F15D12297335C6D227A667DDFEA -14E5B082645FF8464005DDEA5707EBA80CF90FA0CCB96C0A247D8FFCAF9A4648 -9FBDFF340B538CC0FCBD6BD95332656B9824D0952C90E02253720E3E0C70647D -60C5F1922E2477EF0448BE058DC2FCB89FB472E0903266F5152794CA50E0A116 -340B61F71060BC4F2ED9C4BF309F29431EE95BEF423169D9D0E03169A331A6A2 -DB0EED41340E13D01435EDE36948790414CF873F8B2F074719C4D44A43D7B06B -C18976B508E351BF7BF0049DDF782F9619D03F3468FF29DC92C8A4DB86033C09 -7B02CD02B9B068216E01DE13412B65E827CB83ED82D2DEAF0776026C43E7C76D -4A9EE92CD1208C029DC5D664AF3C4C9078A45ABCB5A6307A86E2FF63D26C7179 -6CB7136FCBD1B7638F62EFAA0A927EF0ADE04B4EC1B806AF39A8CA3293C4DD58 -B686FFD8F591B294CAADC574E4EC0791FDE4DD00AB025A3E5AA3BBDA3D3B660E -EDB98A8E9CAD1E173BFD1EAC3BC928F440EB35808011C7564419340C2B81657B -79C6F991A5C83BABD238D6AD43DCEED8AED855F263DAF26C3B705F819B0A9720 -D8C6800525E32FED9477C99249E98D844BD44E7035A8224384DB9DBD9AFBF7D6 -0C075F24CAF73EF95252DD56B4FC5B8BF93ED63AA64C5C2935B8262F200CF102 -195AEBCF16C2185BE019304467C09189B45698584ACDF6B50958A40658552053 -29F08781EC54D0B6A6D898923C2E6319C7782D758816800434A31DF4EC228531 -2B79FCF0AC8F45AC79AD292EE3F19C0EC2D8386D6DA6F15D187604FA9CADBB6A -5817C27E52F421CF8813016F170AD344FCBE1EF93707B303C02AACEF17CF6780 -2694983D44B6D70287DC9AFCF7CCF836FCA3EA61EF83C9022BDF0778316FC056 -9E058011C93C01B3E5A1C755CFCA274293F0D09CE4A0CB90A880AC368B7551DD -7A84598D6DCCD92CF11DFAAB3366E130ECFF3433E1C20D605FDD853B8C11C146 -4B2DC89F0BDC73B733B5EC6AF2D65019D5CD63F9EFD52B3AD39BFCD12234DCE6 -4BBFA1F6403083B7B9D2C5367393A015353929008694751053851B6069FCDE26 -20E360576557B19F00DDB63711C2FBBB7DE7F50626AFE1DBFAD3244FC6E84086 -D4AC740ED7F8C2985E5D37348E5AAFA19CE6AF4BEECDE29B73703BE65C13E72B -0510C5E745E0EF1EB7F3078131CBF8CEC42259C3AA1A284712E3DFFD8582BDC2 -4F79BC90B538844C421E19529D0E21C37E4F1516721A5141E7811466A92A6004 -6C7BA2F7ECC395F4A49A06003D45437EE57703098933D94E4D66EDC2C6FB0CC8 -9283002EDB304FFC2E6EB852C7F523F23B81458C92CC6F6F6BF7703CF75FCEC2 -832DEB4F686F858BCD83B6C701D8A91256BC2018E9417BA20542485D1B406693 -7779DFC140C8D72B34E28FC69119A55A2CB834810BFB5F9FC6D8E5F78DC4E34B -880A98E2F6F19ED55DC66127E4CF14521DD37FE33A480416A3C46DF6326E03F8 -E1D1CECA352D211C3434F0AA14240F0038134F39345871E8627A17F23ECECAC8 -BB49B59186B7675FEB93DC26C5D5530D063D6E5C689553B4269CE25CFF28BD19 -C4933B006EE2C9339D204D90FFE6EDA7FCA43AA457ED4574FFAEA63F7BCFC490 -4ACDCDFA8ECB68BC462F2A3BF3027F643EC8C766EEDB5371FCDB7BD62556C76B -5F8292366E80BDDA8FDBA25EB5C8003925835E9A67A38CEFA51CE2679E1D9994 -96E95DDF1DFC2F1240FACF4B9917ACA03A2F054D79727D3CE827FC6BA8E04AFF -1ED9F429B7793CE381C5A4FF7085AAEFE5EBCFF4370F5D644681BCBCA2BF6799 -6958603647E863F7CAEDCD0532B246C6D51A54083A727CA0A6DA8422D26C80EE -1B7136B67D648F1BF8950627910A97B345512D2271E14195A0846BB39334A539 -0A3075952CBCC999EB1A1D2E64A1925E2B694B44DAC70A87B882F7A97321BB1F -A22027033D93EF05DC8935629856963A9B713F7E2A266947CEEDD9B7218CBEB0 -7B159082329839F37809BF1B7569C338DCAE47A8A7DA2227EE31CC1A7F7FD500 -676B852B7B35FD85DACD87595617A4338E65D13B5C92CDF5FE785B9D7E088004 -DCC5340A42ED218EF74BD9269DBB01162EF315220A85EAC151C2FD85958E3DCE -75BF6875BD2E155A02C70962182BA15F4236B3D5149DF4BDF3AADCEA68BC300E -ED8461A29830CD2BA0EABE996F54354E183611CCC0AC3DF1CD73006BBC47851F -BB6AC20D79EB0626F4F96F84BB3A6025398B3A085D5AB077BE3F7BC225023EE3 -C3C7D6A5949169C72B53BB57F74742427A4843FF350450F982D22EAFFF72C301 -1126BFB8582A72C52AF3CFDDA8C2EE986116312C22E286A3D2ED3F7957DC2317 -1F34D2CD12267998564E36FB252F0347770844018A932EB150E717D3D0BEECA4 -9AC4836FC416EF53F647066C556AC6D9B4CA303B8017713690BB56B113C5E3D8 -E039C6DE30254FF88D1B351587B7EB0CE6C4AE7C9D2D45DDB3A03246A71C24E5 -E6609C148CBBB9AD277E1221629F11FCD92F630CFC7235F36F3C3C4ACF4C1446 -7FA699D138DA34836BBAA17E5BA59D46C118C24C0C21CAAAFF106BD36A4C2D72 -B2582662BA090C048639DDE988B8DC4C86C8221F45DFD99B4EF405F2C1DFD36A -D3614CA8E9954FDFDB8E2F14C7930AE9160FF6E5A37C40844FD80C1BF54D6AA0 -6927C8A5047C9944CAC838D3797C6D99CAAA59E57A5266AE2CAE7268397360FC -5B11110AB30BCE42FF90D6FDB31E67B9E20C21B5724A8E424770BDC0573F0803 -1F5025B329C1DFA7B166B27E7291852AA190DAFA5B3A6B6DD0C67976DE2C63D8 -F2D2647EECC08038C68A5B23D822563F0A8AE7981B87B758E9E3A8B6D136A95C -02AC68D058A91C2FF91890769F3D2F234DFFF3C95C205B90AE71F9F5ABB4829D -7A7D3F7FB773DA48BB134D6F7E6BA21F989FC50C94F40168589E9CDF6F1DB938 -D7D0A5791047A1A95E36C57EF76DA4C83090A807839CA259289FFAF93F9A9943 -B84E1F38F1E8108671C934C630D863D719E445C3017FBE237BA0D776356D707A -8368C52C6812BE1F5CB89B6A24CD866141E0DA61F382B4B071D45EFC3D471897 -F46AB31592074A576A783D73AB836D9436FA5169CF36FADEBD017E80FA42D20C -6E3A11C9902DFED908C8B71281EE6914C96A27225EFD11CA2DE3001CA98874EC -55246C343EFA8CFBCE7F34D31ADBE83C8B6413282AA9A76FB5E7EE5742334F6B -E3BD7CEEDEFE09E8866ED503999B5F9FF26F5E6663D2D66CA1BB6670358E0F57 -1E9698BC9D02AB49796AF49791965D7BE5EF93A1AE87796397A4CF573A988B39 -07E08E0DEC35C6A30571E01CFA4DD0B8A42420F68D02EC261F0CAFF84F3304AE -FA1103BA4DAFADF34CA66DBC315F9029266180456119168D8B7A92D4006494C4 -151448DDE1761B2409EC818EF4456D02FE36A19249D0B98843559CA663712576 -D3044379F981ECAFD57E62C370BFB00A42C68CB17C4E547E4295333B57E96D31 -DC8816137999362A2584B18EF3B9A3B0DEBCD81AA48905E3AC54BA71C218D676 -E30C15F5BCC53F3DAB5CCE248C21804AE4ADD87CBF925EA149FE6CF46AB36E71 -743D676FBC6901957BA638847092AD2F2E2304C42912A80AEBD2505817CF30BC -7451440C403F4712D3997348B384203A0AB3CCD11733AE00D826EFED57A51A2F -4B9BAAB3F7546951A0E6A11736349EFE6B4A64D0DE57E7FA7B58C9B718F745A1 -2C226D307E5C48E4C597DC1EB4FCCA3958A5E5B0D3A126C87838C53ECA4EEF1E -8BE53E6D1E8416044D0813EB03FB0913F78868BDB63635B43F9774CFE94D1ACA -B14AD42D9CB613FA353B79FEE4D6E3DEFEB831E73B10D81976C9B3F245625355 -490A405591C9686D3333CA129BEBF4259D617A958C1C0590485D236084CE7F27 -E7B0428356D46B3DBD39BEDA6B26863BDE02C95ACD47F0820B5B63BD3A7AE7E2 -08F40AF6148BED135A0C1CEEE63F81CD7A60067F8ED5BB263FA82483A7311D30 -19A3075EB8EE4FB203EA350451B395BF518CB8E5E2C7356096844F9C0AA59DAB -E7645BFAB3BFB77D2CAF4135C7354683A42CB3FC8A7DC18DC1A5044AB9BC863E -7EF1CC1E9631760002D05DE570C58006B25AD8162906B1DE9F30178F2098F31B -10709B0683750F9E7174E9C8E68A80F402ED0C6F4BFF8F4890DB54E021DFAF3F -E0CD74FDE13B0AB90033040711055037A38251FD967090268E4FD54C44339FAF -888B8A04EA78252587D027AC9938FAD62C9108E6A90F1C20761452200CCFD4FC -50F494C2D6EF47FD8D186E868D116E0315F3470926BE6759EB65FCC4DE544669 -E365C6B8D8962040546E8D213B3EF29E7F61C9EC6A372E8C3FCFA5485808E75D -E5DA0903366388A0B6516397B504ECFCC31060C5837EF6BB1601036990BD9B5C -F428D2A11F659ACDC887C618A8AFC9DE9A80BF93EC85209DD1C820CEFB992B22 -7DD4952BFBB4E6D46AABD43719AD3983DA9FD51AC36763A251EACCC1B3F7574B -BF775A44077B0592C4441AE38C129A2F2D9F4D1291970DC5804360656464247C -C4F89E8AFA955C1AFBEEF2D81EBDE0C9F29AF95FA7024D7240F853B6337C093A -5243A4C913D18CFE45B0E6E9C218A21F49A1925EC495D452B4A4B1721FF730E2 -5766AF3BF5ED746220B77013C86A12A104201DACAD9E4577518829CA87A7BFD2 -42C346FA1844A8A7DA45AF8F8E3F4D1C7605F0C61F41EDEFE3E7A53697A3DAF0 -248881BFF6C4A95EBBA23D91567F8CF0E7FF5EE5AF1A1E94D9576B0BD4F65483 -F05DDF263100095AE456C73C1F408ED0BED7E4123B38D787A75B0628C37BE99A -E539D721397CEBD9F9B597910EF17DE2F723E1D1610C3CCB0F686A6A20388690 -445F876442A908F97A79A08B355C4627F95B1F1B7C81E3F6FB984A11623B25B9 -65AA110762FB8EFE03A315C53FAF9629D519174379E63DED655FBBD0D358F887 -C097AF0DFA080C66BF8819C70B08640ADB5FFBCAC694FCE068696109541B5496 -84EF000066979E771AA50C37794012730065CFF49D04AEA701F98AB962043311 -6B8FBD4917960E063BF7A1DAA86A031FDFC4323F9ABF93EAD39FF3522919996B -94491B74F8BF602E60DE55B1DDD72546E9F8287585FBF5F68271A0C39EC58FBD -E97054F69640222298D4208AB7462C6AC620E069DD0BB151F69F91DFCE381046 -B52244499E7445A83E926C141A1D9891B44F589BCC556EFAD0CE120D2B77BEBC -1508FBEE25F51EED7FF37E95D0CD3DF0544CDC9A667E950A948A898E00001A0E -E8595C0690DD7B499668A18C035C77DAC92F6C873C07B879634FF06E7571FDF2 -F850AD08547614417B4CB3968997DA761EA00C03A5A1F715E2E56A3FD96A21AB -A5CD946BC53C77A970D8FF4B5EEF317497DD7B0619A0C44CA0AFBA8EF9A651A1 -6A70E9D217831C713F44CBBD9F637B91B2D92955349976C4E08B54B5EE2B6E10 -51CE863BA200E10D9FB3806BB73022497B9AD2F8BD5433714CF74E117E84BCA0 -8EDC0594B1685FA85183E83CC0A2007ED34892FB1880CDDDE933FA8A63601992 -90CA54F6B0BE2D8EFD6CFC1D8F3EF6BC8BB80D01F10C3A33C4B41F0C2C60CB2A -BFFE9FA1B00A9FBE46D464F2D3B6766A44A78DB0D32F2D6D933B20F918BACB94 -C9D8E1550FCCAFEA4C93CEB0A8BB05DD8BF39E48CAAD98A5F9027151B44ECC01 -2C1BE2D7D973A5B201FCFCC659E97B5BC819BACADF7A7DB67CBF8A0F393369BC -A26EAD8F90961D07250ED8A5402C4F72F172A4CE35B71CFE3F764562E326FEA3 -D3F12F64CC425C6B00A56D288CDEEC65E1BC3F1D083784F4BEC8442DE85DA7BF -F842741A08ABCBDA543C79C75CFB952D9442D1614F3CD04ECBB89811069960C4 -AA5002E21848AB34640320415C2077BBEB66D817E62E89AC38F4B9E4252DC10A -9EFC95BD2259EAFA269D8BEF6AD8AC5865833DB29173B370CC2D1359AA8B2C0D -000DA61128B0FFE531375C82C737AD4A368A14F12D1EBBEE931AC3020687B7A6 -28C6A024DFB237BA48F662300DC7601BF92DF0AFD64E7378519CA0E66206532A -5CFB31877873542CD9632275AABC107A3EB369ADD004DC2C8292899B7D6E878A -7304CB5A2387B134D035702740D5ACD28A36A3461ACC346B2D99CE2172603EE1 -7D435C490F6B26B87AD0206B09DFBCC4362AEE17177DC24264EAB729BC137A32 -F3733BB551DFFAB1BAF9215865763626312B0D932A9503C3034F330E4A6F9441 -CF5A36669B8D95BD56035BF4B0481F85CD5178A29410106DC02CB34D3D86B369 -BF58D8514376C01A5B779A495AA02BC97A38D37B8CDD807B518402465F3BE18D -125D58C4F5A8BEBA262CB8364198F776D853AED675B2F1154D875D2F096455D0 -6FEB898279FF466D6E793DDF6A6AB497822B9F32587E61AC8247AB8F2512C767 -FF410A00A3DF8CEFDF143AF901F613A2667062123312ABDFD5909A8D36A96CD6 -A66A395EA51EB79BAC860FA5E6F85608F209E9A17022D41F634F28ABE39F81BB -9F60FAEC0D2127F70A4CC9E0295670469DDD692A92565884892F103777E96C62 -338E6536D168694DFD4F1762F19F5918CBA69BC8F40AFD341D6E559ECD0763C7 -EC087264D67FE89050673651258D9538D097F8E860750A00337EBC7E82DBC70A -691ED823917AA2C02E26043455A6F5BCFB9665FE10DE6D77E0052267BECCC8FC -46DCBDBA5B8A439D4D5DE1768CA3DCCC46F205FCBC9A016997EAF31D26EF6CDA -5B2631FB0DD5C14284768AD0988482D9A7BFD14876F4F98E830DD13DEBE6FA0C -14460CB4D26B70F5DCEED8495841E63EBEE6FD719B42EF2DF840A752274E8586 -53A7F2CEE375CD4E17EAE42D9AF307177A63A6E965DA75A944989116A204F863 -16CD55C3FBA9C734A8B4B48B67DAE50CEE031825AF16910AA9CB845C578911B7 -AE06B4E470DC12D10F0174A07D2786AD3229FDA38E108A184648BAEDA8A2C96D -46F97A3AD5A7AEE1EE991E0092C629C79AEC55DC6F89ED7EEF8FB89DBBC79F31 -E5FC4735CFAC8CC542162E7B259879ACCDC88A665C8363A6E576A30959EE91A7 -5CE26209034590EA4004C37E0F4160F2455E87FA8A0E8E887B1CE31F4228F6B3 -E72B80A73157725969F85AF4BA759058C83B1EAD499A0AF185F5CA8EE586F4EF -A498DBA5FCF920CB4B8AB70F64F1502CFA38F0DE37E70C77CD20A114C022837D -4A45CCD382E8E20EB46BDD86FDC84CC8DA812093A59F5375DD10B9320803632D -5C5B4077172564E7AD22606B8912BDBC030CA5008A5C9CDB7E5F1012D19AA4E7 -CCCD5B8E96039691756C8BC9B8BE11D3A4AC1A3EED07255940AD377ABACD8F54 -F40A8C82965C4E528553B092C07DF3FADB5C278A6F7191EB83FAE2624648A590 -2B4FD334B7B7BDB16DE42C2E4811C516742BD6C2DF388F48A054B4DECA0E7C08 -715C48A0F291BE60EEBBB8A4D944ECFD9AA6A4411BE3F8EC1E227C641C735623 -BBBC9B4F9D4B7E2E813417EEDCDF6F93057BFEA470D27713D040A72D040FD956 -63FBD41E0BFC5AF2A8CE5D00A153134452EB08CB6CB666C537A59034693BFAA1 -FE2B8E673F350ED301C92AE947E5433FB69B2C47F557A05E4110A5E4544D3B20 -DE7E7B58464B04838DD35D8FC7F6136BD2D9CC31A097829CCC2A04ECD45BD3D0 -185B750FB5EF74E2C8CE8BF46B6A10D7BD4D7F5CB1CDDC027D792239208049FE -DA70A010D90D92F0CA88EFD1ECDD62FCDF42A4B1008EE3865424200DCB953D2D -E512F139FB2CF9406BF151240C5B6C81A7E67654E06E3CBE15C9D6AEEFC4FC47 -BCF07D17EC242DCF941C72D710EC20AD29D933BE6BB0002ED66D44823EE30832 -5C0ACE6BCDED02DFBF15817DFB2FEC22732B5C45CF586A04D0070B27D4FE3E89 -4FA3545EF28E1B9E7589358FBD2856A7EC288A2CD360EDC451832D242365FE4B -DEA5493A2FDE704C9D5DDA7A9FAC1098537753DBC5B411892BD7F66AFC048233 -202519CAE41BB96AA7041095C2428F1E624720A66F1116C7D88A4BFCD3A1BB5A -41F4FDA69B5310567A5694A180A36BE761D7206D1B0795D5DB7D2FBC11DD2541 -A22F34BC8D78BD96B11B93955FF0AD1542374697DD471B752B3323C219F1E2DD -DA8A8AD29E70F5B234A541E57E882E14E3C0EBDD149FECF29B744E6941C19C78 -2D0E15949678DBFB51895320086146E7F79239DE4C94DA96153AFD5864299F28 -E3EF76610BE89A7B2361A8B87E92FE1E5F53B1A81C0BFF922481A7B2621813B1 -693DB2852343C9779C0A60FB33A8409D84609DFC4DB7F577F9783FCD063E4605 -B8EFBDFAE586FD5F2D0867E32E9C7431A01D3AD8FA1D52B8123D553805AAD481 -83052182E0EEB7AA85088989A5B0FFB8D63CAEC98DB2124AA136A99B47CDB067 -69AB34BBAAAA55A9D98FDB51EF7D8280C81DB38A1F253F69440F1388D74BB46E -BA00AB675D00841720C4B4FD3AFB69626EDD52225355DC226FAAF56B7E4B86A2 -4CBC6E980687CA1F44EE488D1AC6A8BB1011DCA708FC5175749F58A8316A2E25 -28532F69555FB425000B71C15A319F0B03F8000DCD0566E79658FC6B7B467123 -E61A2BDD05347E690E1A1D34B9563F7B1307968C79388E1613BA3C90A54B0058 -EC23755091C2532A30A38AA8BB9DB82A9CDEC8361D00930C6B9BAF912DBB696A -4D73355BC9D9D5654594AAB388369194A6A75FC2898C8D284AFA69527A7FEC23 -FF4FB20F07CB8ECA397B7769781CBAFBD0885EF8FD2A33E7A5BD060E4D52D7C1 -6F85B4356BF65EF47C9537FD81BE2352A8894540C14A05C073D82675DC30508C -573305FCE04F205517EB553E5BD2788198CF441EE54EABCBD2FA114A9C84CA47 -AD9462159DE85DC93159F7FA5ECD3AE4CA45A0E18362483EE1CB9E71B8456A30 -8DFDEFE9E44B42B6A4A1BAC8AF96269F0095CB4E56C96314F66BEFEB785A1DE9 -7DAAEED67404B6101F45178089798899A3CE2079C9D29AB90BB4900D9C4E662A -5E55FF6C7C62B86A55C177B5FD454F4629C366B4FEBFA112D86A43EFA87713C8 -84C2FEF59166E4C4CB341BB0520CEDC2E6D01C9B280ECD9CBE3FEC12418479EA -873BD2A10C0EF4C83C41AC370B8F1B6295345E5B65FFABF332B3E419BF82FC6F -4F580DE106A30FFC75882362E3A64796948F0397410EC914E85DDE698A9C3444 -0CAE230AA1B6DD69E0F717CC203EE5D7909CDC1D08829C1D6E29E6AA21F98093 -D4324C74BCC52B27F7F721443F08A224F078D91502EFFD34E5C1E69AE17A5492 -F854247C97B2A39F6E0EB9BC7BADA892A04A01E6135849996023F1771C1E9C42 -AD4FC5D9A1EE0852625D76C3DA48943A3427F00FC78977267A7B13921853E3FB -04B5E66C306827588ECBFB11B0E190451FD9984A9CC22116D98262502419ED4D -BAFE76FBCA7D7E1FD03D48AEA39115EBB3E6460C5A823BED732611F646E7D35F -4F8F68D60CF4BCA905067D1871F09068BEAD7D121634183BCE28E3AF6FB34009 -77964CBE33776508A0D3DB0EE0810FEAC20B160D09514E83C176DDC6740E10AB -7171BC3D3F5161369EF7AA6DA15643726374AD34CCE963573CA825C640289505 -2A767AA0EB2B4487F19E1B116B2D66772793D446D459B18B18BEE612375D89C6 -CCAF18482520BD01AED9A9649530E65E4DF66D3CA4F7E085231611F8B6A3622F -74EF464BA18A89E24010BD68B06E32DCF25FCE690C15FE54F6FFEF321578AA53 -7A564D647B5BC7E99D7F3D38F98F46409D57BB8D4089D5B48CA5CA21E35E9036 -9FF18B641CB467015B4994808F9A036464C61C5449B4FC2080054D56D451756E -B36F9DCBA193AC98A0803471677F8B424FFCF8F9E193CC0491B8A2191C398E9A -CCD0E834A35C99DFBFCDD7F0C607CBD5FA8F085EFAF286BA80D8F77E0FF006B9 -0DE3BA33F3D940859C1E5694BD105C12F70F479B0DBC9196FD4EF6A48BB68BB0 -72F3BFCC3721BB667008F5C966ECC1D6B9923422F537F2303B8529E1CB3D43E9 -0C46BAB38F9CAAFFAD98B7A948917B5A626D625FB91E07A1835EF42754CD76F5 -F09A04E939DA2DA88ED3710DA018A45014CB1AA076DDD0AB5D6F4FC8358BD3F4 -26EC7C761A2F602D33A4834ABCE4B2B9CA455FD3365844C8D9E16876E6CBA97B -70E0344A5A59B4211BAE10FA74589378D26748ECF773C6485624D3B6329EB094 -2677E9176E437DE93591C105768F4ED6B77C92785B7CB099CCABD0B586303C8B -96E47B34BC06F0217B161D7D4D47C5A1628F4F7072F4BE06A3CAB87CE44780A7 -360B11E1F094A96D1D9AE5A6877E74B19EC55F3E63B68CB19674969AB088F1C1 -CEFEBFA131D7FF66379C51DEDA64758DF0F9C0DF80A274D0109377815696B4E2 -DE26E631F1F3D25A6C186A2673E82CD9F9DB6469C198E1B671D9C385769982E8 -C9FB5B18C865E28C8D22AEDA22FE6176EC52B8EC1150A65CC4FFE3BA50D532D1 -ED521B0AE14EB4E3D3B03FBA9A423EC1762D21C4597DBE1AAD7630835A1AD09F -FA05B35F4C02C828D4D61D6DB3D49C78907C1438A02FB291E8E96FCF9CAA3FDD -793BB28C46F6E3499653B36C0C55CCAF577748690B23CCD82F3A396EB3AA78E1 -F7BDF1E5B6DE264AE54AABC3A787870794236496FDDE3DAA1F0ECBE2088B1E89 -B68AB4744C99C51AA794C9555CA8E82532ABC95099B4BBA2A906A8E4BA53BEB9 -D953452E46AEF97522717F0783AB68B74CBABCE4BD2C8388DDD20C07BA047844 -AC05A42809BBA280A56C5752C1AE1EE2746464EA296F3408A9A93EC0D147723C -729771971BF111FAAD4F09FE5EB10D1560D505FBF1AADAADD0937F2F0CB9BC4A -31C1051B70069DAF9D7582440784948D35F6AC6A75B6CD94F07F24B7B39BCD3F -4E4488DA405182395A6D5BA496644E3B9657B7E5CAD273044D125EE2156140C3 -CB926C353E0DF48B1B27C94A5B3F27FE991E74288F8A0BD676A4959BA3BC9F7D -9BC08ECC3F08859AE85DF6047BC1BA78E99473860B3EB80CB5EECBC83071F50A -8E14934DD863DD77B8121BDC99F996C2655CD12C24F4656A77F005FBBBB32055 -2D5920BADF05C3C7E1F42C66293D0BD33591FEBC73708AFD26B07D52B2E36CB7 -7117E8B3E8E4DEA5C38755D9308D3B5EBF6D2857BD350E1E744540D16E876374 -2367A4379649C900754CCA10EF16862084C9FCF1F592F56E25EDE68599D76470 -CACCED78E03A4E33A12E72F0E894E60B76350F27AB0782D637D4CAAB3CEED010 -345C1469BE2122F29253ECBD0A86A161ABFF94A33EF342534687DB784BD2E679 -75925B6EA4E72E5856A2C3D304580F2F5151F3D7140C1E79F2DC5F5E2EEEEF89 -1A71FD3C01513720FF7DAC5424CF836F3EEB04E7D1877012089346044F6E2DE2 -72E1A431BE396B3BF7AAE0CE394080C05C83A6597822E19806CD29B9E0826F14 -4BEC1A4F7E88F31D602E65E56E26954FB2B4C5AA4BE136CCF39236C09AB9839E -B350323CAC694FD6B5A62FD8700496C632A1EA941EE86ABE67E2A1F9804817D9 -5611A3CA766F6B5F67F601E21C6C2213FD72DF6B4C906B62827E8B288D7BA060 -735EFA132BC26C8EFE4D9385B2D73E890A2A7A8C7E5C6D34B8CE5E7220E24A45 -0B44DBEC5E08FE96A28A474836FF1FFB71D478767204E68BD23C2C03A2965E07 -9CA6C9EA84C853FF625180942312B99FB7D23EADBF06FC1827650CDCA19A1700 -3F27A569E8684149AB1F78770BDB9E1AF703312E1FF3A177BBBB06D5F044C1F8 -2168D2FD154448E6D7D3B5CE78A9E77A4666EF7F98EC6E9EB519FFAEFDD01DC0 -CAEA89BDB3FE7A655D5A8EC6145BD15F52C8384B87FEDBD0E77A07BC49854EE6 -494880E45C21CCB56F18794D93B7737B259ADD7294B5DFCCD01B82EA1338C60A - +331BDED95DB0237E9B61C5470AD852E6E29B5F10590B17D84732A89881BB6CE7 +1B0E5CC67B887E62169355A4CF80853402ACA01E05593AC4F9B8AF0277C7DAA3 +C73CF2876DDF004812735D9077C21492CAC2D700F5903C38A6696E3313117BFA +DA771ACAD0FCAFC7C2AEDA0E295BF25D0D26EBA2C6A021A497CBD9C97B6E4824 +FF55E97E02B5EA08F7FD881872BA01943CDE78F9F955602A19913A2D74B70271 +CCB67ADD09E59194C8C3204C0F35141E13E2C5C57944DC8551285E69E5589425 +741E2493B1B52CEAB33434404BDE500E925B622C14CCC3D694AE8AD23A7151DA +64D1FBEA77DA66FF3AD8D569D9BD332A929211C4DDF4867FAA83BF646CA892E5 +474C8CE82D8339E506BE98767DD801B206D11F7CED16F85C19917319354321E5 +346BBC282FCE2D18B5261C1B6ADFE426118DAE065C9877C27E7A1A7D9D9384D9 +CBBA8D68EC552C49FB0D8A85A1294DC6C5E166F49B5C678D94F43FF424D3BF18 +769FACE24A2C8EB06438FDE0DF8A7F51728843FFFE74D09EC4BBB31BB5F1FE98 +A4C7743E711572964D1E91F3B40917E547F9E5E40F26110E9343DFE2D9CA5693 +B134D2F206FB6DC79979741F9B6B34766F41A27999FBED494F889177E8204034 +AFBE2DA5D8897A638F461AB15A08F1419714AC2439BF9AC02A1A60D0BFDF9F04 +3F3503F98579FA71ABEDA722EA92AE5A5CF7FE4EB5725366D3F2EE2E625A5721 +1D0B366DD75485FB9E7A121873F8B8A0A137FF9A522C762BA989D907899DDBD6 +AE35A72497D27E802F69ECB6D0EC3504865788686400FA7271B186165655F44A +615942A347317A7C4CAC8F5118DAA871362EDE0D2DD3C214123EA0C6FD0C9C7F +FB61C785384EBEE8A524F22C2DBE7594FA0CE1562E10D42A2F9AC88389FFA8FA +51668D610778DBBB12778B9FE33D22E501665E74FACFD97EE55ED69050DA7094 +ED2C496A37F32C0EF855AC8F7D0B1C62D1FAAAE56B3F52AB145E3719BB1D0856 +91125D2BB45DAC746B9D5200F69158BBC974DC150DE43733E2F38BCAEEBA747D +77C7F5176F70487AD323CBA9522FB9F8B9339248EDB400B1A8CD82BDE2FED084 +ACF4786B40ACA8F5D8A47AFA17219AD75CDA35B59FFF5F13F9FD64ABF1DC796F +F777DC6601D96A5FE0C647C57863BC215A4B46C7619243EBE351C073A237FEFA +BA2E0DE1F2E831684752E67A8AFC263DBDEC7DDB39F049D056D6A4733F81D315 +A78C787559635D989E987583365D54BEC59CCA2CF0365FED877D4C822797FE9E +A1FD17D425712AC4803EA6194587388E6ABF91A83921CE07892CC3856E5DF930 +6408B78108C50BD6CAF8C4BA9CE127B033EB706D028703C800BA581A847E300E +9083EDC68BF2FD0FA6667E4CFD36F35D4C80BF94F1BE2D10500DA5063BFD7573 +D7DD001A3D7AB0662BB21579AA7BE27A8882FA7899EA68870A247AA339B17806 +871521BB328102BDA22069DD9C23057D2708F4B6018AA8AC4D06EC534FC82F55 +584540D18D7255CE4F6A6726F6FDE81112A771D4E14B5E27B2E8432B5A28D496 +310D18F6753AF457BA427449ADBCC67BD5A21EE06E2980DA758B6FEAA0FF3058 +8DD86A11FF16A7769FC4650D3629067BCEE306294C70761FA950207CA81881D6 +B4C733AF1E3D7F983D8071FCE7784FAF8AE07CE379385EA76D9DBBCC4444E2D3 +9A5FAB370C55CCB9A77D5512F7BF1FAAB5032C6E2A68CC2BA565EA855E7DF665 +9A9D2A661A46EF6D98FF8413933B203A7D4B9EC476E12B4440A69BA3B84AC19D +9431358FA15354897091D518C8E8002944753A616B16E6822A6F7841BC42FF68 +66E5E3AE7E6231B019BBB2CCAC0DFF5AE3F5738AACF6D7953D2435E444EBCC04 +A64799501B5E2EC1CC0368A6328BFD559CF365EB84EB72AA0F714ED1F884B54D +347428510FD2FFE076FE338315441AFAB7ECE8857673BFB584EC880466161406 +2C0CF6EA6D9F7818A0AACBFCD1BD7D5B4EDBEC23924EC00E4528C3855056409A +750BFE527E2FC47FA797FAD191118993760CDEF09EA8CFC979633000D0F872DE +5678CB884EA5E9007EE910C590DE029685E07033ED966D5E365803D36D9B6BE0 +50D007693BABD27CBAD5062FB53C620CD32A7F7DEC8E2A64F6E2B0B7CB46E07E +F4F3F4227B294530C61DCBB3CBEF7D5E021E75E2282F5077B04C5BDEB580A748 +07C401890AB3F921EA44AA2B71E861DEB6DF349ED40EC55F3C8C529D7F90FEF1 +683131E9A5C9392A0E5979EC13BD5C2DFB63C92E5B499F5D8B6BAD5842EB68EA +71939B3E6D83742EA0D43F0DEFCBCEF91FE661C9A5B9AC723F007D304274E967 +1FA57E9B879E2187118239BB57459552EF65D13D8C7A0B4CE04200FE87D51BC1 +A607959AC3A1F048CF7DA79F967DF2475574412D685B5A12EEFAFE025010B427 +85FB0D1C2EF436A589EBB4383B44DCB7A36953A7C1A2AFDF9750AC677AA1809D +1D78C0665F8954914AB2A3DDB0238D3C3B0E5464A846B55544D806D43FA4F394 +E5054ED5E8C984D50AA10F11B1F7F87CCF34C743AD42856C0218B737094BF855 +7C45DF8B00F7C5845946312FE87C799ABCE464F9AD60125C865337BE2932D2E0 +0A485EAB0790B2163656EF31A39DA7A6E712C3895FB6F1AC597E5CE8FC65F56A +0454CA486FA86BD25F75FF7FECFD3A8EDEED183DC9AC468DB44AC4A5D6F32042 +F003D7B5077AB6600B2052D3C78497A4C6510E3955B3372B17F51D976312B6D8 +A10127E5E6AF4D6952B9D89E2FA5A407EB5D494FBC2513A7210446AB7A50197E +5D476E0DEA1E088481296FD4FB97246EFFFF94392A8F73715B8E69FE4C750A4D +E62EE2CDB3A8EF1540FDE3F21DDCD38E1E5C2E4502A4D46700D90794F622A8CA +8A4CED301B6711DA47FD180F8AC2369401F3E68ACD31350DC642F47BE04DFAF2 +AC97C7A89859ED36863EFB64509D6A1017DA7A4BD45313637B2445B0A915B642 +44578430B585B63D58B9E05C213F99DF01BF8915DC1FC7BE0E4DD4016B649F94 +20EB1089A34318F4821F35C7D1F1DA848653A444CE5989A8B07E5CD4E72C6BE3 +544456CB9D4E0E350759CD0837DA696841FB33DF30CAAF16F512DF535C9CC440 +14071AFD4B2E574F274D664D8681E889612215D06EC9148AE11F0506E8D37C7B +3C661EA6AC4939EAF7F8FAC2FBD3CCBDA38C45968A0084919709F6661D65810E +941C2DDFA6D22FB452006958A05C85E1EEF76161F7E87A501383437F0AB71C28 +2DA329D741871A66F528AE15290D9CB39D92198531639A2C9EDD40EF5CA1D880 +31E7A49D2F7A757BC34607AC8087E214BEB58AB1F663BA0ADDBC7F6E451A6D9F +3E52601D4D8ABE22F2131E0FF023BA443D3AB647CAB96D9C83F5D9631830F86D +EABE8E2E8E1EBFEF5AD3B0586560C7F43B068A06C7CFE71AF2E6BE4DD96A8473 +952E3E7EC82431E5284B02309F995292B728A7AA13BCC9CF582932725ED45CF6 +A3397B43A1021C59406301E869336290142983240B9AD722974AAF472E288368 +0010D33684264D9AEAB9F0F940D32833167EDCBDA9D816CDD57623CD8FFE4575 +5A9F6BBFE61BC54FF2DC8A8A7AE0C24671DA6B601540D3C015B3AB52BCE07DB5 +15BCC7BC827AA9D41EB4BF17E92391749EFF5AB36ADD9F306DD8149149A2F79F +CC26E50EE5A5267AF762D603096D7C6107E52EE99358AB3AF5EC1129B28E7F96 +85B28C5A4A58E61894A86811D1237178040531FB4E428FBC56CA52CDBA76FEE0 +1281B4C8F5304B162043F4CD24B07AA02CEBBEFBA7B4EFED765B893D1AB98DC0 +63F4D68C3377093999523D869F0C1BFDC5E45FB902558DEF37EFD84C9B98A297 +C9595596F45F051AE4AFD561208FFB44A34CD59DF854545D2F7E6275DE353C70 +D187874B37731F93C80D923035A155DAB1A8BCC8871785329BD75243FA8EF13A +17550A080E323FA0DE7A101C4526D9733C7F1F0DA9D9FC46F6A33CDC869B4FC4 +9BE951E93DB0B814A309643716850DBA07B85DF9CB82FD0B61908B7B5448BFD0 +42667F94FA7E4F0115EFBD5D03EAAD9E0DBAE4A196CC4FF866F1B9AB9750AF96 +7E8BE893A6D504DFD3591E3A068D074E974DCAA08320268A0DE427F4A47FAC59 +3865ECFAE63FF7931807E574FE042C40B4208815C47FB69D9F55E48AB6D879E2 +8E7038567C5BD4072AA99B554D88162384508C337BA1AF64AB82BA6F8FCFC0EF +4367AFA64082096E8E0C8D9B178583634C96F7A880EE4B2F57C4CA1A69FB657D +C6E97E05A598BC786EDE7E8C72A3BA3E78F6210F741E4217401D012CEAD74B17 +80131AE9DC3D83141BD7CED6022AC8D8437B09E4E397E1A9BCB632695352B578 +500437F2DAA6E55ECCC6926969C6BD5F9AE6A44BCFA53473D3D930E6946A24DD +DB488E916E3483CA49C470502B31E26C32DEA51CCE4A7F8A7E7674D919C7318D +28AE73A0513288A4DBEFF7E86019AC749FCEA2311B6CE750A2E6353860276996 +0501AF775E4D2698303DE45B6986AE3936969C90D25F7304C39F99AD1DD2BEB1 +BEA50F4D432B102A8C8ABFB0E86A81C4E5FF89CF84A286359DB347B0F18BA445 +D6DE6F50D694974EE85474988EC20214937F516C22F97635DC25834711603CFC +C079AEBC0B6DDE984567C3D0999618A1EB459F9A47CB5ADAA120DA01F6D3D35B +EDB03D85601E95CF38D9137AEF2080583E99749739D4B5EA93F605217D1ACD8F +71E5D94ECDA80E8D15415CBB8259CD19736274F90B394880CCE12A0849F4B4E8 +EFDBDDF7634DE3CBB0861583FE705C5CC345AB95057BB5170E956CDAD655F1D4 +5D58543A1B1C4CB9F575B69CD186F42E12914C0E5D15D6A208287FF249DF019F +FCD1B83B10793A2A0D62A6C51F9E5A984C2008BA42A52E88F6595D230B469EAA +FC1897C15913FDF0E4AFA8020F9536B730CADC918A48CE4EDDC70CD5E5CD2B12 +E0A70AA7DCC1DD9210C3BD517C1DB6708BBC5970ADA527D7AC5F2B98A38C0B44 +2EDD53F71AED9BA2291ED55DA48969E6151BEF2067C3BFFA7D935A2A82D5AC0C +10C9CE09B5638EF500C895AB800FB59F0495676FA17BD5734DC82B8543638CCE +6C51ADBC522387F535C68BB36B0727C0EDADA952A533A2F909D3AC7CB73233B1 +A8B9AFF81ACBB15F6CAA0C6BCBBB97EC643CCC1487F222611D126C38FF45356F +863DB871799809A3470FA119A9A72807CFAB9D0D7D74AD35F7C6DC9989819D37 +C12CE0C48E14C76A6D0ED2FD635456904862F84DDBC610966948549CCB54ECA7 +C0E984B19F911F4EF195676CA2E6008E38566F38EF49D4AE4DF9BC5699213A9C +78F600722DABE9AEF6FBE54B88B9A36C2AB73085E40F985EF659CE540A4851EA +3810CF958231A29B2C5674091A85EC404551BF71EEBD4A7E350B9E4553A893ED +ED4E1161247558AC3D10A94B12D065909D2EBC7ADCAC6A62B4E8F8AE8B4F5CD2 +4BC21BBA62A5A4D151770FAFC34A28AF385444C8218721BB6331BAF9F2E68142 +8DE2F203CADE1AB21944DF743AED3512F89679E7F24CB460C71A61488FA504BE +D150A2522C691F561B766038C4E902A36911CAEF0C2A080FF35036C8E8138481 +30E70EB2B78B2D9FA3C9B109B713DB0E791FA20B5231C40971B123C000F6E1C1 +1C981B093B26E95ED1C83D262309D2FC48BBA9DE45EDA7F5EFE9C29FB832D6E8 +8896D1D9829AFF0E13AB985B53B613DECFDB0DD36A7CB0271DF89967D4B461F4 +34FEE8B2F45B01DB93C99859CF18E8AB9785F7AD9ED688F12866F7B0A8345FAA +60A04652AF039C1DD9AF699B65C0CBAA7EEF97D0E62558769F7D956BE53F7DD1 +62144D198A6A041ED69D0AAA3EC80A64B671896A2B6E94F6DF8F6EF4CB508513 +23C9F32BF540F9A0B524D6B8E598E7FD662654B1538096466F9CE198EAFCEAD6 +B78B968016B8F2053C35A46EE535A7F4A5A7831531171057F6ECFA5446AE608D +4A1E793F12218A909880508B4A43A0AC239BF1E820EB97EDF35B8FB996C569C4 +1C898C0973842B630FD86A705F79A5C8039C00BFD81387D95BE1C7DE4C725BD8 +83151FEB655498449008DC9883F680B5C7B2FAD9B6DD951F23258172A911576B +6542113DE34D761C9AF4833CDA601F2610F3AF60EB5B5573AEA297484CB11212 +4FDA56536DC3F00505348F6F36F98EE07FC2DDADB764ED2B77428A6EB76C83F3 +2B574EDE42F3FA8B23FE4A3A45660E40B7CADEFD677707E070038B808257412E +529D6CABB0926AD74723935E7C9C8BC17BF0FEE5307638C0863759FB70881283 +B9002119E1F52298F08BCB0388D10F3F9000FF92F8EDC45BAD5ABDFF6F4CB832 +E5E965CFEDC9E31D2931B9578FC2C5220BD39AB3A2B0417519DC14AF86D9AD05 +5A465DE49214F10E43E0E3659EC3C8143465342860F257A51F34D9E21E118467 +AC91403EC5C4D63A2163AD4088AB77941551FA308E62B700400FD8CA01E482DF +857840D9B4C2BC8E4DE735B4FA1174E2910880DF7F1CD4BE35C410D07FF90D45 +E2171127D5E07680546F55CD443D2564554844D538168C750432FE66A54979E7 +18CC8A8C0BAF2FE429817DBC67BAD3C206DA6D296D3F5CDB61A00AF1E47AC49B +D7568E9410DBB3132907080842294FC1FFB41142BAAD5E4912E41E9A08266A18 +D5F4761B0F335867D4ED7CB6845152DF94E4E2E9116F5FDBDC3BDCAFDB2B88E8 +53D4BD8C48728B0358CB8B3F584A171323ECE4D7190095BE4ECC74E22C95A151 +8023570CB258DC1BCF686EADC2019948DE03DA49D54D3EF8ADDCDE48DAE3B9D1 +F1642C93A1A6160E27F6236CACD9B9086556DB6339ACA02A4E2E679E57339DA6 +324B40046934CC6B895251BE08CB7B327F55E68A61591614B72294FC707CB217 +EE6A62D24E3F1701DD223804EBA9B5669B5FEE16B10B5FA261702D8265238C96 +6E6256F3C894E6C9DAABEA3C40A3E01568A932A9459CFA90390863EB490C82CE +F508B396E01F157A7997A1CA9B3A6F7EF02EC3E41C9D3FB2B114B18E32E81539 +6FF54E5792924B867C8B771E1B48C4F1012B8D67B01B4D8AAC0F2642ACA48483 +EE206AC2B65D2C936D37932F5F77D33127ECC1AC15D3F37CF37CC71FCB12DB47 +A2BC1C97495F0A3693DDDC640B0A4A8840F68B9C67CD75B7F66A3FE35B4C05E9 +2CB68DFCA5F0F496F5DDFF2DA9D21168D94CAA7158DC81BA4C95D12F91BCE49B +5A5ED084F8B4BDF0A31DEEF72A8E0AACD28DE78961E948C88342172BFA830103 +256B676F93E96EBD2B6DF491C120FE30E09C40F30E10F1BB219A31EEB6890DFB +F738DD12D7394B814D4521715625C46CF5F0D2B056AF572BE47232178D9F6203 +D76E3F3E51D97CE2BC7B745631ADCCAC9BA2DA8D4C81AB350F0307D4537D63C3 +2E1D827292FF5E91E147A84010ADF1A1BB223D748CA9912E815814D1E2069F4F +C3304530F4DDC4EA68A2B91016C5756F0CBCC32B517DBA7A6D0270F0846657B3 +E74D4BB9158F802BD249CEB955F9D4A38B6D768DB5FF10B0E1AB54DA1A4F600D +A7E0BBB975FF9C260FD44D072D6804B6C5D62BAD4C9E7BA56FA905D6D56D8D1E +7B8311156788C2B49CF8FB16FC036D1AE84DCD605CBA9928C02F297B02E68C41 +3BBAFCA51CAED8C47D807D5D41777828687B3FB91D7434F65DFA47582421C58B +847CA8169CFBB5C9ECAA2CA3FE58635486FABBDB01B147E19CDC4BC81F6110D9 +8395EFF66CA4FC5E05A307C7CFDDFEA5CCC454630CEAAED59EC3E2970FEA9AF0 +468878CF5DCA04D357A468FA12C5743A21C41F2FAA73747F9AD50782E2F2F8FC +DC2C86BFD7C0305ADAC0030E0E84CED21FE75AFF6A3AB2E747B7B1908122AB9F +FB8930F5E0BD63EF3A85EF8F3E2C38EDBB6C9CF86E795E200E12890D41AFD6A8 +CBB2D555545A99BA813B54B8B116BBE7123F1C8055719A469E21552AEECC3979 +F3582CC06E24B9073F839119150B567B30FE0917D5FA2D3C10060CB6AA7F1F69 +218DA10B3AACC968DD6D12596680BD9E3E78DDC28FEDBA693887125A0C9584D3 +D4A811685134D8205205EFF32292A4FF85201037A4CD23325FA15F0F059D02AE +3F35F17BA9946734AEE8E28D51B97B31CCC64DE7D73A86DDAFEDDC4A0322E448 +EE8ED01515439D7F0859BEF8ED00D3D040164D8B0417D4BCC9EE14D625D2B4A4 +0ABF457B3451C7B2FB8BF4F80ABABAC0C98EE35C1209AD81B52D40DEBFEDE07A +D6FAE5E0E8C4EFBEB62ED6E6A89A9FFB5E8CCF7062E4BDA7EB8C2D07DA2C0FA9 +26FE6ADA6EBC703E61470EB892796F91BFCE9E23D41412B56020A2688BCF86F2 +E05C87D413198252970C88248AA4D946A1C200E445D79FA2D4F03098B6417AAE +FDD537071047549A975ACE7920D2C2536F92AFEA2BBCF818AE2AF27AEE408371 +8B64A58140852723AD00612EF05A2FE516979F6854232CC81B94A16C5366A8B3 +F788E0A9A5AA651D802B542420E129B3C09D0DF5FF32C70FABCBBF01662B7F12 +202F2412D589E6F3BB43A666EC00E24489DAC0B8217E0295BD21A45A6BE8D945 +3D0BB06552D320B0587900B08E4E1F2DA7112B42F10C2A00CF04752305E6A570 +F7C52D601FF6C9E4F3277B783826FD085460E230CA6859576DB7A1083370D039 +D28474ACDC28A76D4ACB308ACAB098A2FDE2ECC5FFE7D2D047BFDF41C3210595 +B4D87DF60BF5CD96BB18F8715C091DDBE18466C03DC2449E4148D4ECC9CD98B9 +E9EAB3CECC63AADF6D129F1668206A964944E019EEC4C71D78D6EEF4ABB0EE68 +0FB5289A1FF0E0E0C70AE07E23C26A64F4027BEBE1CAE9CB4C6032D9FB3F8A54 +C357757CB385D6428BC0D10DF57DA11802F0AFC38AE5DACDC22CA1E5ABDC99A2 +E7279366F04E88423BDB102AA3E3A27250D197F433BA4B3400F5F0A4F132EB06 +B620262D55B9E9925E598F74B98824E8C54DC5F6846DBF6BEA470DC58CD439CA +080D59B774D5B32F7A3C4A722394BA8FDE24FB41BB67171B4B29A9041AE08046 +F0287B9B68B00860512D74DD7CDB3FC225C5C886EBF5155D29360651EE01B99E +6493AEFF3CAF965C3658E5E913C019CD06DE217EEB3E934050EC98FFFC2EBF55 +B968CE012D59C418A94D9B9F4D817E034E88D1565DC5FC61D2A42142A47BB819 +F2228A1DC45046945B0715B272C80CA0A315DA413CFE4B1AD73A2510462C44C0 +2BE31E13FA8888A8B422485272D9B945EF948CA42579A05BFDE90B81BD77D0B9 +ABEF12837C2F3E2337E05AA8ED4EFC432B4881F6AB5057F2039F1096B1CCF583 +8FB0D014F345B65D53C4AD85CB8161F3B50D33A626BCA6AB7207B74E1A863D8B +5968E5C6F4D34797037FC3F96214FCE52064F82DC644CB8634EE27D5169D2EB5 +AD760D429D14A59444E38F2CE13218A7EA652C0EF7B56AFD1F637D61B32BADF6 +7C89E49D611814700E17FC6D184B640076BE54C7E4FD56EA4AE68A014ADB58EE +1CF253649CC15041A50F8E662482EE989AC02D55597E5C6EF19BDE66838151BB +51A3046AD68FCF4D00C8DE89D09C2FDAE413A319759CD9A6A6A119FE17EE41E2 +E1B58AC9BE8F9E1192EAE2D57F9A92550687D2818986ACCD61214F2B8AEAFE3A +F3B26B4899ECB9789C047D6F2B1837D74531FCC5D90BF69E0626DB74F1218669 +5AC9F6903DB02449162F1B9E20578814CA89C49D2C2150913E65C7B42E979A40 +64CD6DD3F4C011BE570A4E996FD5ADE1FC7173429D53CFD38B7BBC90F460BFA0 +40BD6C53CA9FAFD047413685211A1EBEE008108B4490A3DE3A6753B19E0A6D80 +49F03F7BC2086080040D2CDF12B8A383AFFA99093F75877AC340F60DDD3F32B9 +A698B6F7BEFB128AE0742B15EFC754D5F03C81B2D6BE5DE4EA8C6DBF7BAA51FC +F928E49C9AFCE074FC327C1581665455A95B0CDC6B055319BC7B27B42E771ED8 +8937EB70B4F5D1FF49BB2EC7D7BA2632878B74208A8C98A0741ECECE9D2E80AF +4C65540C1F2CD038D9E6D6994DDFDBF675E32BFC08540F3E7BD685F5C3D60361 +C81AEF5DFF0A5F458116FF82E1909C8FA6837EC2E065A1492CDB9C6A9931C4DE +9B02FD8AAFE8C66E00AC021B713C2191795CFF353EBF6D33B347694B0CA86214 +C0078B1657B3E239B92820E3BBF2F49D32943F4E75D7023BCBCE08C79B1E9ED9 +CC48BBDA6C08DBA4A93E09BB0703D35BB16ED8D2CA3ED93171E96C87CA081599 +817CD16A3573F4303B4A81F24D0524D54240313B970DCBCBB87DF3EF5572A6C4 +E1F939A6A896A14995B6C2680726007934DB7614EFFDFB1A8762D2A9A09F37AA +49305FD4F170314DEA28357BAB2282670BB05323E14A61B4C6E54DE9DAB18EFF +61E13E44B318D1524605B6E5C3543690F81AF6315B353DA7DEA4A1EB72588729 +54919DFA5CE393183FAA8EF1DD1725363B34E4EFA46C1079474CE9F05375BFC5 +58566C8B269C5349348F170067AF2EEA1639963345B9957F7F57974C70865092 +F6C05B6EE23158E391DE002F2289E73BF06EFBC1CB5FB452BDC8C7BB498C2018 +ACE55530E6A152EE1F7245B4235387FB6A91F8E48BC3049268CFF28A498B124B +E96C89274760C4F1ABE054AD038998F3CFEEF3CB07A234B2DE20A3D86E645FE5 +6C701247B7E2E7294E41DBD1A697CCD5B2543E4F2A7FB0812519933187BBCB68 +87EFDD13B32D8FEFF54780E4D89B95EEF8D67013723FB9FA8780500EA9D0BAF6 +E8996A9FF9B53599C92A0404AC54CD8750042EAC6890A557CDF45EA035DC7AF2 +8E2D8FED2FDEDE0DBCDBFE47AFE896262D8E2062B63C543008F53BA289DE93EC +D2E5E6EC8BD8C52C315C674D6EA3FAF1574CA0EBF8AAD1407BA26D8F51F35F4A +21019B88841B930F1DE4A6B50AF5F4B356165484B4B436CF9E1424D11F99B6ED +23C2F991B1052C811533EA61D07EA1637359609664A5750176D4CEACA81C10E1 +E77FAF7DA7E19638860A3255780C06781C09977962855857B6583296AD19A11F +48853D51A7F5FF7E27A7B6096E7B66F149005AB9FA485901EE7F169B9A0A75D1 +B94FC63EC5E5B0D33C5B9EAA6A1A15F524A01F551F6442D88C9E97B54C642B1C +5AE26805C50EFDD0462AD729A8B80147BB08878F206818491D2A5DBE2826A426 +6475D2EC217F768A09F0984FBB06A244642D40AB39DB490237C398C314108A95 +EA0029B1999F7687DA7A7FD820C81CE2D7FCF7A78A302B3F6824C319D2F2C36B +17481AAF88BD9B2B7EA2D6CA34A585677D56E5CBE188504AE3F8304EC961E614 +97FD87D5107E39D922CECCCEB345E3742F9A662618390CB7945A7048245BDFAC +D15163BC23DC3A02EBF79A4C0EA4E14B9E2C07B4E4F6882887613E1A51947D2F +EFFD5ECC473872A30FEE970B13F692EE166C729FF0A1F2316A9E6D95F34CCCA0 +4E286A96C01D86EC79767C07F37DD8D208225789A161FCF9617BBDB69E7F294E +F1D8ADF4AF08237B20872C5BC869685A619D78BE9D663DAAF1F03D511D69AC1C +401EA73B22A4E2140F0DF42E6B8BBD6BCD9D5547C6F3D896DB35EA8EFA677211 +A308A6718C8A98C5A1D5407EC955F0CE4DAA19E73D823D5D73D923A6663B4E5E +92DAA28A4A32229B31F7E100A2720CED9BCCB822844DB06DE24BAA1E01CC52CA +126E542F9457F5FDD6EB589E4000ACBA80849097A100B5D58815234198A6BA6E +638CA45061D067ADE0EED91D235A5C69948CC89FE9C7573ECD003373352EF9BA +0F429F4BE9AB8BBD7977841BD0BE33C49423C76FCDBBE1D5382A867E1C39BB96 +A5036E26D8494BB4F4060D18844AA19F507C42250F0A65BA65FB7DF8F8A20550 +165EDDDF1E12C1BE82774CE4E966266650032555CC3B1947CD36C293B36EB0B3 +54BD122DCFB9B40B1569185AC0CF3D4E87FD52A207C4911481BC738DE7575364 +5D8DED6BF68FFA011FE6EA2AD4A2303E746830C195D3D2175287D040AF12BCAC +9195F98AFEA06DCC3FDC4A5116C02E0A17AF41E8B46847F757C061E2053E9D9A +4778D5623F767EEEA91B487F2B3246DC7F0841B0FD9AE0BED1100B040E829D97 +8CF320B6AF28DAACDCAC41298409A566125E733DAC9A481F2CBA27102198D324 +6E162D6B7DE24C3F3FACC3BBB349A270C9B46D8CCB10043CC1F634AC351069F5 +DB205BB77DBC71A13FD802D0B986A96CCC8F5A8C0D9563AC0CC7FA4094A10B43 +933B626FD6AC61F8E826CA9A91D864B0E7F1D54B0E5EA829FD208B5FCD50DE05 +E8C043C51F067B1B32CA179E6E92E20570B77DE34F5813BEE67126A9A9C8DDC4 +201C37FE981ADE97A89BE9911298B3F6F587B205 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 @@ -3467,8 +3471,8 @@ TeXDict begin 39158280 55380996 1000 600 600 (pip.dvi) TeXaae443f0Encoding ReEncodeFont }8 66.4176 /CMMI8 rf /Fg 132[56 50 59 59 81 59 62 44 44 46 59 62 56 62 93 31 59 1[31 62 56 34 51 62 50 62 54 10[85 86 78 62 84 -84 77 84 88 106 67 2[42 88 88 70 74 86 81 80 85 10[56 -56 56 56 56 56 2[31 46[{ TeXf7b6d320Encoding ReEncodeFont }53 +84 77 84 88 106 67 2[42 88 88 70 74 86 81 80 85 9[56 +56 56 56 56 56 56 2[31 46[{ TeXf7b6d320Encoding ReEncodeFont }54 99.6264 /CMBX12 rf /Fh 134[71 71 97 1[75 52 53 55 1[75 67 75 112 37 1[41 37 75 67 41 61 75 60 75 65 9[139 2[94 3[92 101 105 1[81 2[50 1[106 85 88 103 97 96 102 12[67 @@ -3507,9 +3511,9 @@ rf /Fm 149[28 2[50 50 31[72 1[77 4[77 34[100 6[77 77 TeXf7b6d320Encoding ReEncodeFont }32 90.9091 /CMR10 rf /Fq 139[41 41 43 14[46 58 51 31[79 65[{ TeXf7b6d320Encoding ReEncodeFont }7 90.9091 /CMBX10 -rf /Fr 134[62 2[62 65 46 46 46 2[59 65 1[33 2[33 65 2[52 -65 52 65 59 10[88 5[80 91 4[60 3[76 2[85 83 88 8[59 3[59 -59 59 59 59 1[33 39 33 19[52 4[59 19[{ +rf /Fr 134[62 2[62 65 46 46 46 2[59 65 98 33 2[33 65 +2[52 65 52 65 59 10[88 5[80 1[88 3[60 3[76 2[85 83 88 +8[59 2[59 2[59 59 59 1[33 39 33 19[52 4[59 19[{ TeXf7b6d320Encoding ReEncodeFont }35 119.552 /CMR12 rf /Fs 134[83 2[83 88 61 62 61 83 1[79 88 133 43 2[43 1[79 47 70 88 2[79 11[119 1[88 2[108 6[56 1[125 1[108 @@ -3527,12 +3531,12 @@ TeXDict begin 1 0 bop 350 976 a Fs(Solving)52 b(Systems)g(of)h(A\016ne) f(\(In\)Equalities:)70 b(PIP's)1528 1183 y(User's)53 b(Guide)1603 1479 y Fr(P)m(aul)37 b(F)-10 b(eautrier)549 1726 y(Additions)37 b(b)m(y)i(Jean-F)-10 b(ran\030)-52 -b(cois)37 b(Collard)g(and)h(C)m(\023)-55 b(edric)37 b(Bastoul)906 -1846 y(F)-10 b(ourth)38 b(V)-10 b(ersion,)37 b(rev)i(1.4,)e(Octob)s(er) -h(18,)f(2003)1770 2177 y Fq(Abstract)638 2309 y Fp(This)h(do)s(cumen)m -(t)h(is)g(the)h(User's)f(Man)m(ual)h(of)g(PIP)-8 b(,)39 -b(a)h(soft)m(w)m(are)g(whic)m(h)f(solv)m(es)501 2421 -y(P)m(arametric)h(In)m(teger)f(Programming)g(problems.)63 +b(cois)37 b(Collard)g(and)h(C)m(\023)-55 b(edric)37 b(Bastoul)884 +1846 y(F)-10 b(ourth)39 b(V)-10 b(ersion,)37 b(rev)h(1.5,)g(No)m(v)m +(em)m(b)s(er)e(8,)i(2005)1770 2177 y Fq(Abstract)638 +2309 y Fp(This)g(do)s(cumen)m(t)h(is)g(the)h(User's)f(Man)m(ual)h(of)g +(PIP)-8 b(,)39 b(a)h(soft)m(w)m(are)g(whic)m(h)f(solv)m(es)501 +2421 y(P)m(arametric)h(In)m(teger)f(Programming)g(problems.)63 b(That)38 b(is,)j(PIP)d(\014nds)e(the)i(lexi-)501 2534 y(cographic)f(minim)m(um)d(of)h(the)h(set)g(of)f(in)m(teger)i(p)s(oin)m (ts)e(whic)m(h)g(lie)h(inside)f(a)h(con)m(v)m(ex)501 @@ -4624,373 +4628,381 @@ b(alues:)p eop end TeXDict begin 19 18 bop 257 266 a Fj(3)98 b(USING)32 b(THE)i(PIP)f(LIBRAR)-8 b(Y)1947 b Fn(19)403 573 y Fm(\017)48 b Fl(Nq)33 b Fn(=)28 b(1:)43 b(an)33 b(in)m(teger)g(v)-5 -b(alue)33 b(is)g(required,)403 767 y Fm(\017)48 b Fl(Verbose)35 +b(alue)33 b(is)g(required,)403 776 y Fm(\017)48 b Fl(Verbose)35 b Fn(=)27 b(0:)43 b(no)33 b(debug)g(informations,)403 -961 y Fm(\017)48 b Fl(Simplify)35 b Fn(=)27 b(0:)44 b(do)32 -b(not)h(try)f(to)h(simplify)h(solutions,)403 1155 y Fm(\017)48 -b Fl(Deepest)p 864 1155 31 4 v 39 w(cut)33 b Fn(=)28 +980 y Fm(\017)48 b Fl(Simplify)35 b Fn(=)27 b(0:)44 b(do)32 +b(not)h(try)f(to)h(simplify)h(solutions,)403 1183 y Fm(\017)48 +b Fl(Deepest)p 864 1183 31 4 v 39 w(cut)33 b Fn(=)28 b(0:)43 b(do)33 b(not)f(use)i(deep)s(est)g(cut)f(algorithm,)403 -1349 y Fm(\017)48 b Fl(Max)34 b Fn(=)27 b(0:)43 b(compute)34 -b(the)f(lexicographic)h(minim)m(um.)257 1524 y(W)-8 b(e)22 +1386 y Fm(\017)48 b Fl(Max)34 b Fn(=)27 b(0:)43 b(compute)34 +b(the)f(lexicographic)h(minim)m(um.)257 1590 y(W)-8 b(e)22 b(strongly)h(recommand)g(to)e(use)i(this)f(function)g(to)g(create)g -(and)g(initialize)h(an)m(y)f Fl(PipOptions)257 1644 y +(and)g(initialize)h(an)m(y)f Fl(PipOptions)257 1710 y Fn(structure.)45 b(In)31 b(this)g(w)m(a)m(y)-8 b(,)32 b(if)f(some)g(new)h(options)f(app)s(ear)f(in)h(the)g(future,)h(there)f -(will)h(b)s(e)f(no)257 1765 y(compatibilit)m(y)k(problems.)257 -2020 y Fg(3.2.3)113 b(pip)p 762 2020 34 4 v 41 w(matrix)p -1130 2020 V 41 w(allo)s(c)38 b(function)257 2204 y Fl(PipMatrix)54 -b(*)e(pip_matrix_alloc)257 2325 y(\()g(unsigned)h(nb_rows,)360 -2445 y(unsigned)g(nb_columns)257 2566 y(\))f(;)257 2756 -y Fn(The)c Fl(pip)p 631 2756 31 4 v 37 w(matrix)p 974 -2756 V 39 w(alloc)f Fn(function)g(allo)s(cates)f(the)h(memory)g(space)h -(for)d(a)h Fl(PipMatrix)257 2877 y Fn(structure)53 b(with)e -Fl(nb)p 1042 2877 V 37 w(rows)h Fn(ro)m(ws)g(and)f Fl(nb)p -1889 2877 V 38 w(columns)h Fn(columns.)100 b(It)51 b(\014lls)h(the)f -Fl(Nb)p 3419 2877 V 37 w(Rows)p Fn(,)257 2997 y Fl(Nb)p -365 2997 V 38 w(Columns)35 b Fn(and)f Fl(p)g Fn(\014elds)h(and)f +(will)h(b)s(e)f(no)257 1831 y(compatibilit)m(y)k(problems.)257 +2090 y Fg(3.2.3)113 b(pip)p 762 2090 34 4 v 41 w(close)38 +b(function)257 2275 y Fl(void)53 b(pip_close\(void\))i(;)257 +2503 y Fn(The)38 b Fl(pip)p 621 2503 31 4 v 38 w(close)g +Fn(frees)g(the)g(memory)g(space)g(that)f(ha)m(v)m(e)h(b)s(een)g(allo)s +(cated)f(for)f(few)i(global)257 2624 y(v)-5 b(ariables)38 +b(PipLib)g(needs.)58 b(This)38 b(function)f(has)h(to)e(b)s(e)h(called)h +(when)g(PipLib)g(is)f(no)g(more)257 2744 y(useful)d(in)f(order)g(to)f +(prev)m(en)m(t)i(sligh)m(t)g(memory)f(leaks.)257 3004 +y Fg(3.2.4)113 b(pip)p 762 3004 34 4 v 41 w(matrix)p +1130 3004 V 41 w(allo)s(c)38 b(function)257 3189 y Fl(PipMatrix)54 +b(*)e(pip_matrix_alloc)257 3309 y(\()g(unsigned)h(nb_rows,)360 +3430 y(unsigned)g(nb_columns)257 3550 y(\))f(;)257 3778 +y Fn(The)c Fl(pip)p 631 3778 31 4 v 37 w(matrix)p 974 +3778 V 39 w(alloc)f Fn(function)g(allo)s(cates)f(the)h(memory)g(space)h +(for)d(a)h Fl(PipMatrix)257 3899 y Fn(structure)53 b(with)e +Fl(nb)p 1042 3899 V 37 w(rows)h Fn(ro)m(ws)g(and)f Fl(nb)p +1889 3899 V 38 w(columns)h Fn(columns.)100 b(It)51 b(\014lls)h(the)f +Fl(Nb)p 3419 3899 V 37 w(Rows)p Fn(,)257 4019 y Fl(Nb)p +365 4019 V 38 w(Columns)35 b Fn(and)f Fl(p)g Fn(\014elds)h(and)f (initializes)i(the)e(matrix)g(en)m(tries)h(to)f(0,)g(then)g(it)g -(returns)h(a)257 3117 y(p)s(oin)m(ter)e(to)g(this)g(structure.)257 -3372 y Fg(3.2.4)113 b(pip)p 762 3372 34 4 v 41 w(matrix)p -1130 3372 V 41 w(read)38 b(function)257 3557 y Fl(PipMatrix)54 -b(*)e(pip_matrix_read\(FILE)k(*\))c(;)257 3748 y Fn(The)45 -b Fl(pip)p 628 3748 31 4 v 38 w(matrix)p 972 3748 V 38 +(returns)h(a)257 4139 y(p)s(oin)m(ter)e(to)g(this)g(structure.)257 +4399 y Fg(3.2.5)113 b(pip)p 762 4399 34 4 v 41 w(matrix)p +1130 4399 V 41 w(read)38 b(function)257 4584 y Fl(PipMatrix)54 +b(*)e(pip_matrix_read\(FILE)k(*\))c(;)257 4812 y Fn(The)45 +b Fl(pip)p 628 4812 31 4 v 38 w(matrix)p 972 4812 V 38 w(read)g Fn(function)f(read)f(a)g(matrix)h(from)g(a)f(\014le.)77 -b(It)43 b(tak)m(es)i(as)f(input)g(a)257 3868 y(p)s(oin)m(ter)g(to)e +b(It)43 b(tak)m(es)i(as)f(input)g(a)257 4933 y(p)s(oin)m(ter)g(to)e (the)i(\014le)f(it)g(has)h(to)e(read)i(\(p)s(ossibly)g Fl(stdin)p Fn(\),)j(and)c(returns)h(a)f(p)s(oin)m(ter)g(to)g(a)257 -3988 y Fl(PipMatrix)35 b Fn(structure.)45 b(The)34 b(input)f(has)g(the) -g(follo)m(wing)g(syn)m(tax:)403 4164 y Fm(\017)48 b Fn(some)34 +5053 y Fl(PipMatrix)35 b Fn(structure.)45 b(The)34 b(input)f(has)g(the) +g(follo)m(wing)g(syn)m(tax:)403 5256 y Fm(\017)48 b Fn(some)34 b(optional)e(commen)m(t)i(lines)g(whic)m(h)g(b)s(egin)f(with)g -Fl(#)p Fn(,)403 4358 y Fm(\017)48 b Fn(the)34 b(ro)m(w)f(n)m(um)m(b)s +Fl(#)p Fn(,)403 5460 y Fm(\017)48 b Fn(the)34 b(ro)m(w)f(n)m(um)m(b)s (ers)i(and)e(column)h(n)m(um)m(b)s(ers,)i(p)s(ossibly)e(follo)m(w)m(ed) -g(b)m(y)g(commen)m(ts,)i(on)501 4478 y(a)d(single)g(line,)403 -4672 y Fm(\017)48 b Fn(the)32 b(matrix)g(ro)m(ws,)g(eac)m(h)h(ro)m(w)e -(m)m(ust)i(b)s(e)f(on)f(a)g(single)h(line)g(and)g(is)g(p)s(ossibly)g -(follo)m(w)m(ed)501 4792 y(b)m(y)i(commen)m(ts.)257 4968 -y(F)-8 b(or)32 b(instance,)i(in)f(the)g(problem)g(of)f(section)i(2.1.1) -e(the)h(domain)g(is)g(de\014ned)h(as)f(follo)m(ws)257 -5143 y Fl(#)52 b(This)g(is)g(the)g(domain)257 5263 y(3)g(7)872 -b(#)51 b(3)h(lines)g(and)g(7)g(columns)257 5384 y(1)103 -b(0)52 b(-1)103 b(0)g(1)f(0)h(0)52 b(#)f(-i)h(+)g(m)f(>=)h(0)257 -5504 y(1)g(-1)103 b(0)g(0)g(0)f(1)h(0)52 b(#)f(-j)h(+)g(n)f(>=)h(0)257 -5624 y(1)103 b(1)g(1)51 b(-1)104 b(0)e(0)h(0)52 b(#)f(j)h(+)f(i)h(-)f -(k)h(>=)g(0)p eop end +g(b)m(y)g(commen)m(ts,)i(on)501 5580 y(a)d(single)g(line,)p +eop end %%Page: 20 20 TeXDict begin 20 19 bop 257 266 a Fj(3)98 b(USING)32 -b(THE)i(PIP)f(LIBRAR)-8 b(Y)1947 b Fn(20)257 573 y Fg(3.2.5)113 -b(Prin)m(ting)37 b(F)-9 b(unctions)257 758 y Fl(void)53 +b(THE)i(PIP)f(LIBRAR)-8 b(Y)1947 b Fn(20)403 573 y Fm(\017)48 +b Fn(the)32 b(matrix)g(ro)m(ws,)g(eac)m(h)h(ro)m(w)e(m)m(ust)i(b)s(e)f +(on)f(a)g(single)h(line)g(and)g(is)g(p)s(ossibly)g(follo)m(w)m(ed)501 +693 y(b)m(y)i(commen)m(ts.)257 897 y(F)-8 b(or)32 b(instance,)i(in)f +(the)g(problem)g(of)f(section)i(2.1.1)e(the)h(domain)g(is)g(de\014ned)h +(as)f(follo)m(ws)257 1100 y Fl(#)52 b(This)g(is)g(the)g(domain)257 +1220 y(3)g(7)872 b(#)51 b(3)h(lines)g(and)g(7)g(columns)257 +1341 y(1)103 b(0)52 b(-1)103 b(0)g(1)f(0)h(0)52 b(#)f(-i)h(+)g(m)f(>=)h +(0)257 1461 y(1)g(-1)103 b(0)g(0)g(0)f(1)h(0)52 b(#)f(-j)h(+)g(n)f(>=)h +(0)257 1582 y(1)103 b(1)g(1)51 b(-1)104 b(0)e(0)h(0)52 +b(#)f(j)h(+)f(i)h(-)f(k)h(>=)g(0)257 1841 y Fg(3.2.6)113 +b(Prin)m(ting)37 b(F)-9 b(unctions)257 2026 y Fl(void)53 b(pip_matrix_print\(FILE)k(*,)51 b(PipMatrix)j(*\))e(;)257 -878 y(void)h(pip_vector_print\(FILE)k(*,)51 b(PipVector)j(*\))e(;)257 -998 y(void)h(pip_newparm_print\(FILE)k(*,)52 b(PipNewparm)i(*,)d(int)h -(indent\))i(;)257 1119 y(void)f(pip_list_print\(FILE)j(*,)c(PipList)h -(*,)f(int)g(indent\))h(;)257 1239 y(void)g(pip_quast_print\(FILE)j(*,)c -(PipQuast)h(*,)f(int)g(indent\))h(;)257 1359 y(void)g +2146 y(void)h(pip_vector_print\(FILE)k(*,)51 b(PipVector)j(*\))e(;)257 +2267 y(void)h(pip_newparm_print\(FILE)k(*,)52 b(PipNewparm)i(*,)d(int)h +(indent\))i(;)257 2387 y(void)f(pip_list_print\(FILE)j(*,)c(PipList)h +(*,)f(int)g(indent\))h(;)257 2508 y(void)g(pip_quast_print\(FILE)j(*,)c +(PipQuast)h(*,)f(int)g(indent\))h(;)257 2628 y(void)g (pip_options_print\(FILE)k(*,)52 b(PipOptions)i(*\))d(;)257 -1588 y Fn(There)40 b(is)g(a)e(prin)m(ting)h(function)h(for)e(eac)m(h)i +2856 y Fn(There)40 b(is)g(a)e(prin)m(ting)h(function)h(for)e(eac)m(h)i (structure)g(of)e(the)h(PipLib.)63 b(They)40 b(all)f(tak)m(e)g(as)257 -1708 y(input)33 b(a)f(p)s(oin)m(ter)h(to)f(a)g(\014le)h(\(p)s(ossibly)h +2977 y(input)33 b(a)f(p)s(oin)m(ter)h(to)f(a)g(\014le)h(\(p)s(ossibly)h Fl(stdout)p Fn(\))g(and)e(a)g(p)s(oin)m(ter)h(to)f(a)g(structure.)45 -b(Some)33 b(of)257 1829 y(them)g(tak)m(es)g(as)f(input)g(an)g(inden)m +b(Some)33 b(of)257 3097 y(them)g(tak)m(es)g(as)f(input)g(an)g(inden)m (t)h(step.)44 b(They)33 b(prin)m(t)g(the)f(structure)h(con)m(ten)m(ts)g -(to)f(the)g(\014le)257 1949 y(without)h(inden)m(t)h(if)f +(to)f(the)g(\014le)257 3217 y(without)h(inden)m(t)h(if)f Fl(indent)h Fk(<)27 b Fn(0,)33 b(with)g(an)f(inden)m(tation)i(step)f -(of)g Fl(indent)h Fn(otherwise.)257 2209 y Fg(3.2.6)113 -b(Memory)38 b(Deallo)s(cation)h(F)-9 b(unctions)257 2393 +(of)g Fl(indent)h Fn(otherwise.)257 3477 y Fg(3.2.7)113 +b(Memory)38 b(Deallo)s(cation)h(F)-9 b(unctions)257 3662 y Fl(void)53 b(pip_matrix_free\(PipMatrix)58 b(*\))51 -b(;)257 2514 y(void)i(pip_vector_free\(PipVector)58 b(*\))51 -b(;)257 2634 y(void)i(pip_newparm_free\(PipNewpar)q(m)k(*\))52 -b(;)257 2755 y(void)h(pip_list_free\(PipList)k(*\))51 -b(;)257 2875 y(void)i(pip_quast_free\(PipQuast)k(*\))52 -b(;)257 2995 y(void)h(pip_options_free\(PipOption)q(s)k(*\))52 -b(;)257 3224 y Fn(There)35 b(is)f(a)g(memory)h(deallo)s(cation)e +b(;)257 3782 y(void)i(pip_vector_free\(PipVector)58 b(*\))51 +b(;)257 3903 y(void)i(pip_newparm_free\(PipNewpar)q(m)k(*\))52 +b(;)257 4023 y(void)h(pip_list_free\(PipList)k(*\))51 +b(;)257 4143 y(void)i(pip_quast_free\(PipQuast)k(*\))52 +b(;)257 4264 y(void)h(pip_options_free\(PipOption)q(s)k(*\))52 +b(;)257 4492 y Fn(There)35 b(is)f(a)g(memory)h(deallo)s(cation)e (function)i(for)e(eac)m(h)h(structure)h(of)e(the)h(PipLib.)48 -b(They)257 3344 y(free)33 b(the)g(allo)s(cated)g(memory)h(for)e(the)h -(structure.)257 3633 y Fh(3.3)136 b(Example)257 3818 +b(They)257 4613 y(free)33 b(the)g(allo)s(cated)g(memory)h(for)e(the)h +(structure.)257 4901 y Fh(3.3)136 b(Example)257 5086 y Fn(Here)42 b(is)f(a)g(simple)h(example)g(sho)m(wing)g(ho)m(w)f(one)g -(can)g(use)h(the)f(PipLib,)j(assuming)e(that)257 3938 +(can)g(use)h(the)f(PipLib,)j(assuming)e(that)257 5207 y(a)36 b(basic)h(installation)f(w)m(as)h(done.)53 b(The)37 b(follo)m(wing)f(C)g(program)g(reads)g(a)g(domain)g(and)g(its)257 -4058 y(con)m(text)i(on)e(the)h(standard)f(input)h(then)g(prin)m(ts)g -(the)g(solution)g(on)f(the)h(standard)f(output.)257 4179 +5327 y(con)m(text)i(on)e(the)h(standard)f(input)h(then)g(prin)m(ts)g +(the)g(solution)g(on)f(the)h(standard)f(output.)257 5447 y(Options)48 b(are)f(preselected)j(:)73 b(there)48 b(is)g(no)f(bign)m (um,)52 b(w)m(e)d(are)e(lo)s(oking)g(for)g(an)g(in)m(tegral)257 -4299 y(solution)33 b(without)h(simpli\014cation)g(and)e(w)m(e)i(don't)f -(w)m(an)m(t)g(debug)g(informations.)257 4503 y Fl(/*)52 -b(example.c)i(*/)257 4623 y(#)e(include)h()257 -4743 y(#)f(include)h()257 4984 y(int)f(main\(\))257 -5104 y({)g(PipMatrix)i(*)d(domain,)i(*)f(context)104 -b(;)360 5225 y(PipQuast)53 b(*)f(solution)h(;)360 5345 -y(PipOptions)h(*)d(options)i(;)360 5586 y(domain)g(=)e -(pip_matrix_read\(stdin\))57 b(;)p eop end +5568 y(solution)33 b(without)h(simpli\014cation)g(and)e(w)m(e)i(don't)f +(w)m(an)m(t)g(debug)g(informations.)p eop end %%Page: 21 21 -TeXDict begin 21 20 bop 257 266 a Fj(4)98 b(INST)-8 b(ALLING)33 -b(PIP)2377 b Fn(21)360 573 y Fl(context)53 b(=)f -(pip_matrix_read\(stdin\))57 b(;)360 693 y(options)c(=)f -(pip_options_init\(\))k(;)360 934 y(solution)d(=)f +TeXDict begin 21 20 bop 257 266 a Fj(3)98 b(USING)32 +b(THE)i(PIP)f(LIBRAR)-8 b(Y)1947 b Fn(21)257 573 y Fl(/*)52 +b(example.c)i(*/)257 693 y(#)e(include)h()257 +814 y(#)f(include)h()257 1054 y(int)f(main\(\))257 +1175 y({)g(PipMatrix)i(*)d(domain,)i(*)f(context)104 +b(;)360 1295 y(PipQuast)53 b(*)f(solution)h(;)360 1416 +y(PipOptions)h(*)d(options)i(;)360 1656 y(domain)g(=)e +(pip_matrix_read\(stdin\))57 b(;)360 1777 y(context)c(=)f +(pip_matrix_read\(stdin\))57 b(;)360 1897 y(options)c(=)f +(pip_options_init\(\))k(;)360 2138 y(solution)d(=)f (pip_solve\(domain,context,-)q(1,o)q(ptio)q(ns\))58 b(;)360 -1175 y(pip_options_free\(options\))g(;)360 1295 y -(pip_matrix_free\(domain\))f(;)360 1416 y(pip_matrix_free\(context\))h -(;)360 1656 y(pip_quast_print\(stdout,so)q(luti)q(on,0)q(\))f(;)257 -1777 y(})257 1973 y Fn(The)34 b(compilation)f(command)g(could)h(b)s(e)e -(:)257 2170 y Fl(gcc)52 b(example.c)i(-lpiplib64)g(-o)e(example)257 -2366 y Fn(Supp)s(osing)31 b(that)f(the)g(user)h(w)m(an)m(ts)g(to)e +2379 y(pip_options_free\(options\))g(;)360 2499 y +(pip_matrix_free\(domain\))f(;)360 2619 y(pip_matrix_free\(context\))h +(;)360 2860 y(pip_quast_print\(stdout,so)q(luti)q(on,0)q(\))f(;)360 +2980 y(pip_close\(\))d(;)257 3101 y(})257 3304 y Fn(The)34 +b(compilation)f(command)g(could)h(b)s(e)e(:)257 3508 +y Fl(gcc)52 b(example.c)i(-lpiplib64)g(-o)e(example)257 +3711 y Fn(Supp)s(osing)31 b(that)f(the)g(user)h(w)m(an)m(ts)g(to)e (solv)m(e)j(the)e(problem)g(of)g(section)h(2.1.1,)f(he)g(will)g(t)m(yp) -s(e:)257 2563 y Fl(3)52 b(7)257 2683 y(1)103 b(0)52 b(-1)103 -b(0)g(1)f(0)h(0)257 2804 y(1)52 b(-1)103 b(0)g(0)g(0)f(1)h(0)257 -2924 y(1)g(1)g(1)51 b(-1)104 b(0)e(0)h(0)257 3044 y(1)52 -b(5)257 3165 y(1)g(-1)103 b(1)g(1)g(0)257 3361 y Fn(And)33 -b(the)g(program)g(will)g(prin)m(t)g(:)257 3558 y Fl(\(if)52 -b(#[)g(-1)g(1)g(0)f(0])309 3678 y(\(list)360 3799 y(#[)h(0)f(0)h(0)f -(0])360 3919 y(#[)h(1)f(0)h(0)f(0])309 4039 y(\))309 -4160 y(\(list)360 4280 y(#[)h(1)f(-1)h(0)g(0])360 4401 -y(#[)g(0)f(1)h(0)f(0])309 4521 y(\))257 4641 y(\))257 -4973 y Fo(4)161 b(Installing)53 b(PIP)257 5221 y Fh(4.1)136 -b(Implemen)l(tation)47 b(Notes)257 5406 y Fn(The)28 b(main)e(problem)h -(with)g(an)m(y)g(in)m(teger)g(programming)f(soft)m(w)m(are)h(is)g -(that,)g(since)h(one)e(m)m(ust)257 5526 y(distinguish)f(b)s(et)m(w)m -(een)h(in)m(teger)e(and)g(rationals,)h(all)e(computations)h(are)g(to)f -(b)s(e)g(done)h(exactly)-8 b(.)257 5646 y(Rationals)43 -b(m)m(ust)g(b)s(e)g(represen)m(ted)h(as)f(quotien)m(ts)h(with)f(an)f -(in)m(teger)h(n)m(umerator)g(and)g(an)p eop end +s(e:)257 3914 y Fl(3)52 b(7)257 4035 y(1)103 b(0)52 b(-1)103 +b(0)g(1)f(0)h(0)257 4155 y(1)52 b(-1)103 b(0)g(0)g(0)f(1)h(0)257 +4276 y(1)g(1)g(1)51 b(-1)104 b(0)e(0)h(0)257 4396 y(1)52 +b(5)257 4516 y(1)g(-1)103 b(1)g(1)g(0)257 4720 y Fn(And)33 +b(the)g(program)g(will)g(prin)m(t)g(:)257 4923 y Fl(\(if)52 +b(#[)g(-1)g(1)g(0)f(0])309 5044 y(\(list)360 5164 y(#[)h(0)f(0)h(0)f +(0])360 5284 y(#[)h(1)f(0)h(0)f(0])309 5405 y(\))309 +5525 y(\(list)360 5645 y(#[)h(1)f(-1)h(0)g(0])p eop end %%Page: 22 22 TeXDict begin 22 21 bop 257 266 a Fj(4)98 b(INST)-8 b(ALLING)33 -b(PIP)2377 b Fn(22)257 573 y(in)m(teger)37 b(denominator.)55 -b(In)36 b(the)g(preceding)i(v)m(ersion,)g(there)f(w)m(as)g(only)g(one)f -(denominator)257 693 y(for)46 b(the)h(whole)h(tableau.)86 -b(The)47 b(consequence)j(w)m(as)d(that)g(simpli\014cations)h(where)g -(most)257 814 y(unlik)m(ely)-8 b(,)28 b(and)23 b(that)g(the)g(in)m -(tegers)i(in)e(the)g(tableau)h(w)m(ere)g(gro)m(wing)f(un)m(til)h(o)m(v) -m(er\015o)m(ws)i(o)s(ccured.)404 934 y(In)c(the)h(presen)m(t)h(v)m -(ersion,)i(there)d(is)g(one)f(denominator)h(p)s(er)g(ro)m(w)f(of)g(the) -h(tableau.)40 b(Reduc-)257 1054 y(tion)31 b(to)g(lo)m(w)m(er)h(terms)g -(o)s(ccurs)g(frequen)m(tly)-8 b(,)33 b(and)e(the)g(gro)m(wth)h(of)e(n)m -(um)m(b)s(ers)j(in)e(the)h(problem)257 1175 y(tableau)j(is)f(limited.) -48 b(As)35 b(a)e(consequence,)38 b(m)m(uc)m(h)d(larger)f(problems)h -(can)f(b)s(e)g(solv)m(ed.)49 b(This)257 1295 y(has)37 -b(had)g(the)g(unfortunate)f(consequence)k(that)c(sev)m(eral)i(bugs,)h -(whic)m(h)f(w)m(ere)f(b)s(ey)m(ond)h(the)257 1416 y(domain)e(of)g(the)g -(old)g(v)m(ersion,)i(ha)m(v)m(e)g(no)m(w)e(surfaced.)54 -b(These)38 b(bugs)e(ha)m(v)m(e)i(b)s(een)e(corrected.)257 -1536 y(As)g(far)e(as)g(the)i(author)e(can)h(tell,)h(these)f(bugs)h -(mainly)f(ga)m(v)m(e)h(correct)f(results)h(whic)m(h)g(w)m(ere)257 -1656 y(not)e(in)f(simplest)j(form:)45 b(the)34 b(quast)g(had)f -(extraneous)i(lea)m(v)m(es.)48 b(In)34 b(some)h(cases,)g(the)f(result) -257 1777 y(w)m(as)h(wrong)f(but)g(the)g(error)g(w)m(as)h(self)f(eviden) -m(t:)48 b(for)33 b(instance,)j(there)e(w)m(ere)i(denominators)257 -1897 y(in)d(in)m(teger)h(results.)257 2186 y Fh(4.2)136 -b(License)257 2371 y Fn(This)45 b(program)e(is)h(free)g(soft)m(w)m -(are;)50 b(y)m(ou)44 b(can)g(redistribute)h(it)e(and/or)g(mo)s(dify)h -(it)g(under)257 2491 y(the)32 b(terms)h(of)e(the)g(GNU)h(General)f -(Public)i(License)g(v)m(ersion)g(2)e(as)h(published)h(b)m(y)g(the)e(F) --8 b(ree)257 2611 y(Soft)m(w)m(are)34 b(F)-8 b(oundation.)404 -2732 y(This)29 b(program)e(is)i(distributed)g(in)g(the)f(hop)s(e)g +b(PIP)2377 b Fn(22)360 573 y Fl(#[)52 b(0)f(1)h(0)f(0])309 +693 y(\))257 814 y(\))257 1143 y Fo(4)161 b(Installing)53 +b(PIP)257 1391 y Fh(4.1)136 b(Implemen)l(tation)47 b(Notes)257 +1576 y Fn(The)28 b(main)e(problem)h(with)g(an)m(y)g(in)m(teger)g +(programming)f(soft)m(w)m(are)h(is)g(that,)g(since)h(one)e(m)m(ust)257 +1696 y(distinguish)f(b)s(et)m(w)m(een)h(in)m(teger)e(and)g(rationals,)h +(all)e(computations)h(are)g(to)f(b)s(e)g(done)h(exactly)-8 +b(.)257 1817 y(Rationals)43 b(m)m(ust)g(b)s(e)g(represen)m(ted)h(as)f +(quotien)m(ts)h(with)f(an)f(in)m(teger)h(n)m(umerator)g(and)g(an)257 +1937 y(in)m(teger)37 b(denominator.)55 b(In)36 b(the)g(preceding)i(v)m +(ersion,)g(there)f(w)m(as)g(only)g(one)f(denominator)257 +2057 y(for)46 b(the)h(whole)h(tableau.)86 b(The)47 b(consequence)j(w)m +(as)d(that)g(simpli\014cations)h(where)g(most)257 2178 +y(unlik)m(ely)-8 b(,)28 b(and)23 b(that)g(the)g(in)m(tegers)i(in)e(the) +g(tableau)h(w)m(ere)g(gro)m(wing)f(un)m(til)h(o)m(v)m(er\015o)m(ws)i(o) +s(ccured.)404 2298 y(In)c(the)h(presen)m(t)h(v)m(ersion,)i(there)d(is)g +(one)f(denominator)h(p)s(er)g(ro)m(w)f(of)g(the)h(tableau.)40 +b(Reduc-)257 2419 y(tion)31 b(to)g(lo)m(w)m(er)h(terms)g(o)s(ccurs)g +(frequen)m(tly)-8 b(,)33 b(and)e(the)g(gro)m(wth)h(of)e(n)m(um)m(b)s +(ers)j(in)e(the)h(problem)257 2539 y(tableau)j(is)f(limited.)48 +b(As)35 b(a)e(consequence,)38 b(m)m(uc)m(h)d(larger)f(problems)h(can)f +(b)s(e)g(solv)m(ed.)49 b(This)257 2659 y(has)37 b(had)g(the)g +(unfortunate)f(consequence)k(that)c(sev)m(eral)i(bugs,)h(whic)m(h)f(w)m +(ere)f(b)s(ey)m(ond)h(the)257 2780 y(domain)e(of)g(the)g(old)g(v)m +(ersion,)i(ha)m(v)m(e)g(no)m(w)e(surfaced.)54 b(These)38 +b(bugs)e(ha)m(v)m(e)i(b)s(een)e(corrected.)257 2900 y(As)g(far)e(as)g +(the)i(author)e(can)h(tell,)h(these)f(bugs)h(mainly)f(ga)m(v)m(e)h +(correct)f(results)h(whic)m(h)g(w)m(ere)257 3021 y(not)e(in)f(simplest) +j(form:)45 b(the)34 b(quast)g(had)f(extraneous)i(lea)m(v)m(es.)48 +b(In)34 b(some)h(cases,)g(the)f(result)257 3141 y(w)m(as)h(wrong)f(but) +g(the)g(error)g(w)m(as)h(self)f(eviden)m(t:)48 b(for)33 +b(instance,)j(there)e(w)m(ere)i(denominators)257 3261 +y(in)d(in)m(teger)h(results.)257 3547 y Fh(4.2)136 b(License)257 +3732 y Fn(This)45 b(program)e(is)h(free)g(soft)m(w)m(are;)50 +b(y)m(ou)44 b(can)g(redistribute)h(it)e(and/or)g(mo)s(dify)h(it)g +(under)257 3852 y(the)32 b(terms)h(of)e(the)g(GNU)h(General)f(Public)i +(License)g(v)m(ersion)g(2)e(as)h(published)h(b)m(y)g(the)e(F)-8 +b(ree)257 3972 y(Soft)m(w)m(are)34 b(F)-8 b(oundation.)404 +4093 y(This)29 b(program)e(is)i(distributed)g(in)g(the)f(hop)s(e)g (that)g(it)g(will)h(b)s(e)f(useful,)i(but)e(WITHOUT)257 -2852 y(ANY)39 b(W)-11 b(ARRANTY;)39 b(without)g(ev)m(en)h(the)f +4213 y(ANY)39 b(W)-11 b(ARRANTY;)39 b(without)g(ev)m(en)h(the)f (implied)h(w)m(arran)m(t)m(y)g(of)e(MER)m(CHANT)-8 b(ABIL-)257 -2973 y(ITY)49 b(or)f(FITNESS)h(F)m(OR)e(A)h(P)-8 b(AR)g(TICULAR)49 -b(PURPOSE.)g(See)g(the)g(GNU)e(General)257 3093 y(Public)34 +4333 y(ITY)49 b(or)f(FITNESS)h(F)m(OR)e(A)h(P)-8 b(AR)g(TICULAR)49 +b(PURPOSE.)g(See)g(the)g(GNU)e(General)257 4454 y(Public)34 b(License)g(for)f(more)f(details.)45 b Fl(http://www.gnu.org/copylef)q -(t/g)q(pl.h)q(tml)257 3382 y Fh(4.3)136 b(Adjusting)44 -b(the)i(Precision)257 3566 y Fn(Pip)c(is)f(an)f(all)h(in)m(teger)g(v)m +(t/g)q(pl.h)q(tml)257 4739 y Fh(4.3)136 b(Adjusting)44 +b(the)i(Precision)257 4924 y Fn(Pip)c(is)f(an)f(all)h(in)m(teger)g(v)m (ersion)i(of)d(the)h(dual)g(simplex)h(algorithm.)68 b(As)41 -b(suc)m(h,)j(it)d(has)g(to)257 3687 y(handle)32 b(in)m(tegers)f(whose)h +b(suc)m(h,)j(it)d(has)g(to)257 5045 y(handle)32 b(in)m(tegers)f(whose)h (size)g(ma)m(y)f(gro)m(w)f(exp)s(onen)m(tially)j(as)d(the)h -(computation)g(pro)s(ceeds.)257 3807 y(In)m(teger)37 +(computation)g(pro)s(ceeds.)257 5165 y(In)m(teger)37 b(o)m(v)m(er\015o)m(w)g(ma)m(y)f(o)s(ccur)g(and)g(ha)m(v)m(e)h(to)e(b)s (e)g(c)m(hec)m(k)m(ed.)56 b(Since)36 b(the)g(hardw)m(are)h(in)m(teger) -257 3928 y(o)m(v)m(er\015o)m(w)43 b(exception)f(is)g(usually)f(mask)m +257 5285 y(o)m(v)m(er\015o)m(w)43 b(exception)f(is)g(usually)f(mask)m (ed)i(b)m(y)f(the)f(op)s(erating)f(system)j(or)d(the)h(compiler,)257 -4048 y(o)m(v)m(er\015o)m(w)49 b(is)f(detected)h(b)m(y)f(c)m(hec)m(king) +5406 y(o)m(v)m(er\015o)m(w)49 b(is)f(detected)h(b)m(y)f(c)m(hec)m(king) i(that)d(a)g(division)h(somewhere)h(in)f(the)g(algorithm,)257 -4168 y(whic)m(h)34 b(can)e(b)s(e)g(pro)m(v)m(ed)h(to)f(b)s(e)g(exact)g +5526 y(whic)m(h)34 b(can)e(b)s(e)g(pro)m(v)m(ed)h(to)f(b)s(e)g(exact)g (b)m(y)h(mathematical)g(argumen)m(ts,)g(is)f(indeed)h(exact.)45 -b(If)257 4289 y(not,)33 b(an)f(error)h(is)g(rep)s(orted)g(and)g(the)g -(computation)g(stops.)404 4409 y(The)41 b(size)h(of)e(the)h(n)m(um)m(b) -s(ers)h(to)e(b)s(e)h(handled)h(dep)s(ends)g(strongly)f(on)f(the)h(size) -h(of)e(the)257 4530 y(constrain)m(t)34 b(matrix)f(and)g(on)f(the)h -(size)h(of)e(its)h(co)s(e\016cien)m(ts.)257 4789 y Fg(4.3.1)113 -b(Bounded)38 b(Pip)257 4974 y Fn(The)24 b(precision)g(of)e(the)h(in)m +b(If)257 5646 y(not,)33 b(an)f(error)h(is)g(rep)s(orted)g(and)g(the)g +(computation)g(stops.)p eop end +%%Page: 23 23 +TeXDict begin 23 22 bop 257 266 a Fj(4)98 b(INST)-8 b(ALLING)33 +b(PIP)2377 b Fn(23)404 573 y(The)41 b(size)h(of)e(the)h(n)m(um)m(b)s +(ers)h(to)e(b)s(e)h(handled)h(dep)s(ends)g(strongly)f(on)f(the)h(size)h +(of)e(the)257 693 y(constrain)m(t)34 b(matrix)f(and)g(on)f(the)h(size)h +(of)e(its)h(co)s(e\016cien)m(ts.)257 953 y Fg(4.3.1)113 +b(Bounded)38 b(Pip)257 1138 y Fn(The)24 b(precision)g(of)e(the)h(in)m (teger)h(represen)m(tation)g(in)f(the)h(Pip)f(co)s(de)g(can)g(b)s(e)g -(adjusted)g(at)g(com-)257 5094 y(pile)36 b(time)g(b)m(y)g(giving)f +(adjusted)g(at)g(com-)257 1258 y(pile)36 b(time)g(b)m(y)g(giving)f (options)g(to)g(the)g Fl(configure)j Fn(shell)e(script.)51 -b(By)36 b(giving)f Fl(configure)257 5215 y Fn(the)28 +b(By)36 b(giving)f Fl(configure)257 1379 y Fn(the)28 b(option)f Fl(--enable-llint)k Fn(y)m(ou)d(ask)g(for)e(long)h(long)g (in)m(t)h(v)m(ersion)h(only)f(\(64)e(bits\).)42 b(It)28 -b(re-)257 5335 y(sults)c(in)e(a)h(64)e(bits)i(Pip)g(called)h +b(re-)257 1499 y(sults)c(in)e(a)h(64)e(bits)i(Pip)g(called)h Fl(pip64)p Fn(.)41 b(By)23 b(giving)g Fl(configure)h -Fn(the)f(option)f Fl(--enable-int)257 5456 y Fn(y)m(ou)33 +Fn(the)f(option)f Fl(--enable-int)257 1619 y Fn(y)m(ou)33 b(ask)f(for)f(in)m(t)g(v)m(ersion)i(only)-8 b(.)44 b(It)32 b(results)g(in)g(a)f(32)g(bits)h(called)h Fl(pip32)f -Fn(and)g(a)f(faster)h(run-)257 5576 y(ning)h(time.)p -eop end -%%Page: 23 23 -TeXDict begin 23 22 bop 257 266 a Fj(4)98 b(INST)-8 b(ALLING)33 -b(PIP)2377 b Fn(23)257 573 y Fg(4.3.2)113 b(Multiple)38 -b(Precision)g(Pip)257 758 y Fn(Multiple)g(Precision)g(Pip)g(is)f(built) -g(on)f(top)g(of)h(the)g(GMP)f(library)h(\(this)g(library)g(is)h(freely) -257 878 y(a)m(v)-5 b(ailable)36 b(at)g Fl(http://www.swox.com/gmp)p +Fn(and)g(a)f(faster)h(run-)257 1740 y(ning)h(time.)257 +1999 y Fg(4.3.2)113 b(Multiple)38 b(Precision)g(Pip)257 +2184 y Fn(Multiple)g(Precision)g(Pip)g(is)f(built)g(on)f(top)g(of)h +(the)g(GMP)f(library)h(\(this)g(library)g(is)h(freely)257 +2305 y(a)m(v)-5 b(ailable)36 b(at)g Fl(http://www.swox.com/gmp)p Fn(\).)58 b(Eac)m(h)37 b(in)m(teger)f(in)g(the)g(program)f(is)h(repre-) -257 998 y(sen)m(ted)i(as)e(a)g(list)g(of)g(32)f(bits)h(n)m(um)m(b)s +257 2425 y(sen)m(ted)i(as)e(a)g(list)g(of)g(32)f(bits)h(n)m(um)m(b)s (ers.)56 b(All)36 b(computations)h(are)f(done)g(exactly)-8 -b(,)38 b(and)e(the)257 1119 y(size)f(of)d(the)h(n)m(um)m(b)s(ers)i +b(,)38 b(and)e(the)257 2545 y(size)f(of)d(the)h(n)m(um)m(b)s(ers)i (increases)g(as)e(needed)i(to)e(preserv)m(e)i(exactness.)47 -b(It)33 b(follo)m(ws)h(that)f(no)257 1239 y(o)m(v)m(er\015o)m(w)i(is)e +b(It)33 b(follo)m(ws)h(that)f(no)257 2666 y(o)m(v)m(er\015o)m(w)i(is)e (p)s(ossible.)45 b(Ho)m(w)m(ev)m(er,)35 b(when)f(the)f(size)h(of)e(n)m -(um)m(b)s(ers)j(increases,)g(computations)257 1359 y(get)d(slo)m(w)m +(um)m(b)s(ers)j(increases,)g(computations)257 2786 y(get)d(slo)m(w)m (er)h(and)e(slo)m(w)m(er,)i(and)f(memory)g(o)m(v)m(er\015o)m(w)h(ma)m (y)f(o)s(ccur)g(in)f(extreme)i(cases.)45 b(In)31 b(w)m(ell)257 -1480 y(b)s(eha)m(v)m(ed)f(problems,)g(32)d(bits)h(are)f(enough)h(for)f +2906 y(b)s(eha)m(v)m(ed)f(problems,)g(32)d(bits)h(are)f(enough)h(for)f (the)h(initial)g(data,)g(the)g(size)h(of)e(in)m(termediate)257 -1600 y(results)46 b(\014rst)f(increases)h(up)f(to)f(a)g(maxim)m(um,)49 +3027 y(results)46 b(\014rst)f(increases)h(up)f(to)f(a)g(maxim)m(um,)49 b(then)c(decreses,)k(and)c(32)f(bits)h(are)f(again)257 -1721 y(enough)33 b(for)f(the)g(results.)45 b(Hence,)34 +3147 y(enough)33 b(for)f(the)g(results.)45 b(Hence,)34 b(it)e(has)g(b)s(een)h(p)s(ossible)h(to)e(k)m(eep)h(the)g(input)g -(format)e(and)257 1841 y(output)g(format)g(of)f(Multiple)i(Precision)h +(format)e(and)257 3268 y(output)g(format)g(of)f(Multiple)i(Precision)h (Pip)e(completely)i(compatible)f(with)f(the)h(formats)257 -1961 y(of)g(the)h(b)s(ounded)h(precision)g(v)m(ersions.)404 -2082 y(T)-8 b(o)27 b(install)h(Multiple)h(Precision)g(Pip,)h(\014rst)e +3388 y(of)g(the)h(b)s(ounded)h(precision)g(v)m(ersions.)404 +3508 y(T)-8 b(o)27 b(install)h(Multiple)h(Precision)g(Pip,)h(\014rst)e (install)g(Gmp)f(according)h(to)f(the)h(directions)257 -2202 y(found)44 b(at)e(the)i(ab)s(o)m(v)m(e)g(URL.)f(Usually)-8 +3629 y(found)44 b(at)e(the)i(ab)s(o)m(v)m(e)g(URL.)f(Usually)-8 b(,)47 b(the)c(library)h(is)f(installed)h(in)g Fl(/usr/local/lib)p -Fn(,)257 2323 y(and)h(the)f(header)h(\014les)g(are)f(in)g +Fn(,)257 3749 y(and)h(the)f(header)h(\014les)g(are)f(in)g Fl(/usr/local/include)p Fn(.)83 b(If)44 b(this)h(is)f(not)g(the)h -(case,)j(y)m(ou)257 2443 y(m)m(ust)36 b(adjust)e(the)h(Pip)f(mak)m +(case,)j(y)m(ou)257 3870 y(m)m(ust)36 b(adjust)e(the)h(Pip)f(mak)m (e\014le)i(b)m(y)f(giving)g(to)f(the)g Fl(configure)j -Fn(shell)e(script)g(the)g(option)257 2563 y Fl(--with-gmp=PATH)p +Fn(shell)e(script)g(the)g(option)257 3990 y Fl(--with-gmp=PATH)p Fn(,)i(where)d Fl(PATH)f Fn(is)g(the)g(GMP)g(library)g(installation)g -(path.)404 2684 y(By)39 b(giving)h Fl(configure)i Fn(the)d(option)h +(path.)404 4110 y(By)39 b(giving)h Fl(configure)i Fn(the)d(option)h Fl(--enable-gmp)i Fn(y)m(ou)e(ask)g(for)e(a)h(GMP)h(v)m(ersion)257 -2804 y(only)-8 b(.)44 b(It)33 b(results)h(in)f(a)f(m)m(ultiple)i -(precision)g(Pip)f(called)h Fl(pipMP)p Fn(.)257 3093 +4231 y(only)-8 b(.)44 b(It)33 b(results)h(in)f(a)f(m)m(ultiple)i +(precision)g(Pip)f(called)h Fl(pipMP)p Fn(.)257 4520 y Fh(4.4)136 b(Building)45 b(the)g(Executable)h(and)f(the)g(Library)257 -3278 y Fn(T)-8 b(o)40 b(build)g(PIP)-8 b(,)41 b(\014rst)f(cop)m(y)h +4704 y Fn(T)-8 b(o)40 b(build)g(PIP)-8 b(,)41 b(\014rst)f(cop)m(y)h (the)f(ab)s(o)m(v)m(e)g(tar\014le)g(to)f(an)m(y)h(con)m(v)m(enien)m(t)j -(directory)-8 b(.)65 b(Expand)257 3398 y(the)33 b(tar\014le)g(using:) -257 3601 y Fl(zcat)53 b(pip.tar.Z)g(|)f(tar)g(xvf)g(-)257 -3805 y Fn(Y)-8 b(ou)33 b(should)g(obtain)g(the)g(follo)m(wing)g -(\014les:)403 4008 y Fm(\017)48 b Fn(header)34 b(\014les)f(in)g(the)g -Fl(include)h Fn(directory)-8 b(,)403 4212 y Fm(\017)48 +(directory)-8 b(.)65 b(Expand)257 4825 y(the)33 b(tar\014le)g(using:) +257 5028 y Fl(zcat)53 b(pip.tar.Z)g(|)f(tar)g(xvf)g(-)257 +5231 y Fn(Y)-8 b(ou)33 b(should)g(obtain)g(the)g(follo)m(wing)g +(\014les:)403 5435 y Fm(\017)48 b Fn(header)34 b(\014les)f(in)g(the)g +Fl(include)h Fn(directory)-8 b(,)403 5638 y Fm(\017)48 b Fn(C)33 b(co)s(de)g(\014les)h(in)f(the)g Fl(source)h -Fn(directory)-8 b(,)403 4415 y Fm(\017)48 b Fn(a)33 b(lot)g(of)f(data)h +Fn(directory)-8 b(,)p eop end +%%Page: 24 24 +TeXDict begin 24 23 bop 257 266 a Fj(4)98 b(INST)-8 b(ALLING)33 +b(PIP)2377 b Fn(24)403 573 y Fm(\017)48 b Fn(a)33 b(lot)g(of)f(data)h (\014les)h Fl(*.dat)g Fn(and)f(of)g(result)h(\014les)g Fl(*.ll)g Fn(in)f(the)h Fl(test)g Fn(directory)g(\(y)m(ou)501 -4535 y(should)e(then)f(run)f(at)h(least)g(some)g(of)f(the)h +693 y(should)e(then)f(run)f(at)h(least)g(some)g(of)f(the)h Fl(*.dat)h Fn(\014les)f(and)g(compare)g(the)g(results)h(to)501 -4656 y(the)h(corresp)s(onding)h Fl(*.ll)f Fn(\014le\),)403 -4859 y Fm(\017)48 b Fn(a)31 b(simple)i(example)g(sho)m(wing)g(ho)m(w)f +814 y(the)h(corresp)s(onding)h Fl(*.ll)f Fn(\014le\),)403 +1017 y Fm(\017)48 b Fn(a)31 b(simple)i(example)g(sho)m(wing)g(ho)m(w)f (to)f(use)i(the)e(PipLib)i(in)e(the)h Fl(example)i Fn(directory)-8 -b(,)403 5063 y Fm(\017)48 b Fn(a)33 b(p)s(ostscript)g(v)m(ersion)h(of)e +b(,)403 1220 y Fm(\017)48 b Fn(a)33 b(p)s(ostscript)g(v)m(ersion)h(of)e (the)h(presen)m(t)i(do)s(cumen)m(t,)f Fl(pip.ps)g Fn(in)e(the)h -Fl(doc)h Fn(directory)-8 b(,)403 5266 y Fm(\017)48 b +Fl(doc)h Fn(directory)-8 b(,)403 1424 y Fm(\017)48 b Fn(\014les)34 b(needed)g(for)e(compilation)h(and)g(installation)g(in)g -(the)g(PIP)g(ro)s(ot)f(directory)-8 b(.)p eop end -%%Page: 24 24 -TeXDict begin 24 23 bop 257 266 a Fj(4)98 b(INST)-8 b(ALLING)33 -b(PIP)2377 b Fn(24)257 573 y Fg(4.4.1)113 b(basic)38 -b(installation)257 758 y Fn(The)e Fl(configure)i Fn(shell)e(script)g -(attempts)g(to)e(guess)j(correct)e(v)-5 b(alues)36 b(for)f(v)-5 -b(arious)35 b(system-)257 878 y(dep)s(enden)m(t)45 b(v)-5 -b(ariables)44 b(used)g(during)f(compilation.)76 b(It)43 -b(uses)h(those)g(v)-5 b(alues)44 b(to)e(create)i(a)257 -998 y Fl(Makefile)p Fn(.)79 b(The)45 b(\014le)f Fl(configure.in)j -Fn(is)d(used)h(to)e(create)h Fl(configure)i Fn(b)m(y)f(a)e(program)257 -1119 y(called)30 b Fl(autoconf)p Fn(.)44 b(Y)-8 b(ou)28 -b(only)h(need)g Fl(configure.in)j Fn(if)c(y)m(ou)h(w)m(an)m(t)g(to)f(c) -m(hange)h(it)f(or)g(regen-)257 1239 y(erate)33 b Fl(configure)i -Fn(using)e(a)g(new)m(er)h(v)m(ersion)g(of)e Fl(autoconf)p -Fn(.)404 1359 y(The)h(simplest)i(w)m(a)m(y)e(to)g(compile)g(this)h(pac) -m(k)-5 b(age)33 b(is:)403 1556 y Fm(\017)48 b Fl(cd)71 -b Fn(to)e(the)i(directory)f(con)m(taining)h(the)f(pac)m(k)-5 -b(age's)71 b(source)g(co)s(de)g(and)f(t)m(yp)s(e)501 -1677 y Fl(./configure)55 b Fn(to)c(con\014gure)i(the)f(pac)m(k)-5 -b(age)52 b(for)f(y)m(our)h(system)i(\(while)f(running,)501 -1797 y Fl(configure)35 b Fn(prin)m(ts)f(some)f(messages)i(telling)e +(the)g(PIP)g(ro)s(ot)f(directory)-8 b(.)257 1684 y Fg(4.4.1)113 +b(basic)38 b(installation)257 1868 y Fn(The)e Fl(configure)i +Fn(shell)e(script)g(attempts)g(to)e(guess)j(correct)e(v)-5 +b(alues)36 b(for)f(v)-5 b(arious)35 b(system-)257 1989 +y(dep)s(enden)m(t)45 b(v)-5 b(ariables)44 b(used)g(during)f +(compilation.)76 b(It)43 b(uses)h(those)g(v)-5 b(alues)44 +b(to)e(create)i(a)257 2109 y Fl(Makefile)p Fn(.)79 b(The)45 +b(\014le)f Fl(configure.in)j Fn(is)d(used)h(to)e(create)h +Fl(configure)i Fn(b)m(y)f(a)e(program)257 2229 y(called)30 +b Fl(autoconf)p Fn(.)44 b(Y)-8 b(ou)28 b(only)h(need)g +Fl(configure.in)j Fn(if)c(y)m(ou)h(w)m(an)m(t)g(to)f(c)m(hange)h(it)f +(or)g(regen-)257 2350 y(erate)33 b Fl(configure)i Fn(using)e(a)g(new)m +(er)h(v)m(ersion)g(of)e Fl(autoconf)p Fn(.)404 2470 y(The)h(simplest)i +(w)m(a)m(y)e(to)g(compile)g(this)h(pac)m(k)-5 b(age)33 +b(is:)403 2674 y Fm(\017)48 b Fl(cd)71 b Fn(to)e(the)i(directory)f(con) +m(taining)h(the)f(pac)m(k)-5 b(age's)71 b(source)g(co)s(de)g(and)f(t)m +(yp)s(e)501 2794 y Fl(./configure)55 b Fn(to)c(con\014gure)i(the)f(pac) +m(k)-5 b(age)52 b(for)f(y)m(our)h(system)i(\(while)f(running,)501 +2914 y Fl(configure)35 b Fn(prin)m(ts)f(some)f(messages)i(telling)e (whic)m(h)h(features)f(it)g(is)g(c)m(hec)m(king)i(for\),)403 -1998 y Fm(\017)48 b Fn(t)m(yp)s(e)34 b Fl(make)f Fn(to)g(compile)g(the) +3118 y Fm(\017)48 b Fn(t)m(yp)s(e)34 b Fl(make)f Fn(to)g(compile)g(the) g(pac)m(k)-5 b(age)33 b(and)g(install)g(the)g(program)f(and)h(the)g -(library)-8 b(,)403 2199 y Fm(\017)48 b Fn(y)m(ou)33 +(library)-8 b(,)403 3321 y Fm(\017)48 b Fn(y)m(ou)33 b(can)f(remo)m(v)m(e)i(the)e(program)g(binaries)h(and)f(ob)5 b(ject)33 b(\014les)g(from)f(the)g(source)h(co)s(de)501 -2320 y(directory)k(b)m(y)f(t)m(yping)h Fl(make)52 b(clean)p +3442 y(directory)k(b)m(y)f(t)m(yping)h Fl(make)52 b(clean)p Fn(.)i(T)-8 b(o)35 b(also)h(remo)m(v)m(e)h(the)f(\014les)h(that)e -Fl(configure)501 2440 y Fn(created)i(\(so)g(y)m(ou)g(can)g(compile)g +Fl(configure)501 3562 y Fn(created)i(\(so)g(y)m(ou)g(can)g(compile)g (the)g(pac)m(k)-5 b(age)37 b(for)f(a)g(di\013eren)m(t)h(kind)h(of)e -(computer\))501 2560 y(t)m(yp)s(e)e Fl(make)52 b(distclean)p -Fn(.)404 2757 y(PIP)27 b(and)g(the)h(PipLib)f(ha)m(v)m(e)i(b)s(een)e +(computer\))501 3682 y(t)m(yp)s(e)e Fl(make)52 b(distclean)p +Fn(.)404 3886 y(PIP)27 b(and)g(the)h(PipLib)f(ha)m(v)m(e)i(b)s(een)e (successfully)k(compiled)d(on)e(the)i(follo)m(wing)f(systems:)403 -2954 y Fm(\017)48 b Fn(PC's)34 b(under)g(Lin)m(ux,)f(with)h(the)f -Fl(gcc)g Fn(compiler,)403 3155 y Fm(\017)48 b Fn(PC's)26 +4089 y Fm(\017)48 b Fn(PC's)34 b(under)g(Lin)m(ux,)f(with)h(the)f +Fl(gcc)g Fn(compiler,)403 4293 y Fm(\017)48 b Fn(PC's)26 b(under)g(Windo)m(ws)g(\(Cygwin\),)i(with)e(the)f Fl(gcc)g -Fn(compiler)h(\(but)f(b)s(ecause)h(of)f(some)501 3275 +Fn(compiler)h(\(but)f(b)s(ecause)h(of)f(some)501 4413 y(Cygwin)32 b(limitations,)f(only)f(32)f(bits)i(v)m(ersion)g(will)g(w)m -(ork)g(and)f(user)h(ma)m(y)f(exp)s(erience)501 3396 y(some)k(problems)f -(when)h(linking)g(with)f(PipLib\),)403 3597 y Fm(\017)48 +(ork)g(and)f(user)h(ma)m(y)f(exp)s(erience)501 4533 y(some)k(problems)f +(when)h(linking)g(with)f(PipLib\),)403 4737 y Fm(\017)48 b Fn(SparcStations,)34 b(with)f(the)g Fl(gcc)g Fn(compiler.)257 -3856 y Fg(4.4.2)113 b(optionnal)38 b(features)403 4040 +4997 y Fg(4.4.2)113 b(optionnal)38 b(features)403 5181 y Fm(\017)48 b Fn(By)67 b(default,)74 b Fl(make)67 b Fn(will)f(install)h(the)f(pac)m(k)-5 b(age's)67 b(\014les)g(in)f -Fl(/usr/local/bin)p Fn(,)501 4161 y Fl(/usr/local/lib)p +Fl(/usr/local/bin)p Fn(,)501 5302 y Fl(/usr/local/lib)p Fn(,)52 b(etc.)81 b(Y)-8 b(ou)44 b(can)h(sp)s(ecify)i(an)d -(installation)i(pre\014x)g(other)e(than)501 4281 y Fl(/usr/local)35 +(installation)i(pre\014x)g(other)e(than)501 5422 y Fl(/usr/local)35 b Fn(b)m(y)f(giving)f Fl(configure)i Fn(the)e(option)f -Fl(--prefix=PATH)p Fn(.)403 4482 y Fm(\017)48 b Fn(By)37 -b(default,)h(b)s(oth)f(PIP)g(and)g(the)g(PipLib)g(are)g(compiled)g(and) -g(installed.)57 b(By)37 b(giv-)501 4603 y(ing)32 b Fl(configure)h -Fn(the)f(option)f Fl(--without-pip)k Fn(y)m(ou)d(disable)g(the)g -(compilation)f(and)501 4723 y(installation)42 b(of)f(PIP)-8 -b(.)43 b(By)f(giving)g Fl(configure)i Fn(the)e(option)g -Fl(--without-lib)j Fn(y)m(ou)501 4843 y(disable)34 b(the)f(compilation) -g(and)g(installation)g(of)f(the)h(PipLib.)403 5045 y -Fm(\017)48 b Fn(By)32 b(default,)g(b)s(oth)f(in)m(t)g(\(32)g(bits\))h -(and)f(long)g(long)g(in)m(t)g(\(64)g(bits\))h(v)m(ersions)h(are)e -(built.)501 5165 y(Multiple)50 b(precision)g(is)e(built)h(to)s(o)f(if)g -(the)g(GMP)h(library)g(is)g(found.)90 b(By)49 b(giving)501 -5285 y Fl(configure)28 b Fn(the)e(option)g Fl(--enable-int)j -Fn(y)m(ou)d(ask)h(for)e(in)m(t)h(v)m(ersion)h(only)-8 -b(.)42 b(By)26 b(giving)501 5406 y Fl(configure)44 b -Fn(the)e(option)g Fl(--enable-llint)j Fn(y)m(ou)e(ask)f(for)f(long)g -(long)h(in)m(t)g(v)m(ersion)501 5526 y(only)-8 b(.)80 -b(By)45 b(giving)g Fl(configure)i Fn(the)e(option)g Fl(--enable-gmp)j -Fn(y)m(ou)d(ask)g(for)f(GMP)501 5646 y(v)m(ersion)34 -b(only)-8 b(.)p eop end +Fl(--prefix=PATH)p Fn(.)p eop end %%Page: 25 25 TeXDict begin 25 24 bop 257 266 a Fj(REFERENCES)2659 -b Fn(25)403 573 y Fm(\017)48 b Fn(By)43 b(default,)h(PIP)f(lo)s(oks)f -(for)f(the)h(GMP)h(library)f(in)g(the)g(standard)g(path)g(\()p -Fl(/usr/)501 693 y Fn(or)34 b Fl(/usr/local/)p Fn(\).)50 +b Fn(25)403 573 y Fm(\017)48 b Fn(By)37 b(default,)h(b)s(oth)f(PIP)g +(and)g(the)g(PipLib)g(are)g(compiled)g(and)g(installed.)57 +b(By)37 b(giv-)501 693 y(ing)32 b Fl(configure)h Fn(the)f(option)f +Fl(--without-pip)k Fn(y)m(ou)d(disable)g(the)g(compilation)f(and)501 +814 y(installation)42 b(of)f(PIP)-8 b(.)43 b(By)f(giving)g +Fl(configure)i Fn(the)e(option)g Fl(--without-lib)j Fn(y)m(ou)501 +934 y(disable)34 b(the)f(compilation)g(and)g(installation)g(of)f(the)h +(PipLib.)403 1137 y Fm(\017)48 b Fn(By)32 b(default,)g(b)s(oth)f(in)m +(t)g(\(32)g(bits\))h(and)f(long)g(long)g(in)m(t)g(\(64)g(bits\))h(v)m +(ersions)h(are)e(built.)501 1258 y(Multiple)50 b(precision)g(is)e +(built)h(to)s(o)f(if)g(the)g(GMP)h(library)g(is)g(found.)90 +b(By)49 b(giving)501 1378 y Fl(configure)28 b Fn(the)e(option)g +Fl(--enable-int)j Fn(y)m(ou)d(ask)h(for)e(in)m(t)h(v)m(ersion)h(only)-8 +b(.)42 b(By)26 b(giving)501 1499 y Fl(configure)44 b +Fn(the)e(option)g Fl(--enable-llint)j Fn(y)m(ou)e(ask)f(for)f(long)g +(long)h(in)m(t)g(v)m(ersion)501 1619 y(only)-8 b(.)80 +b(By)45 b(giving)g Fl(configure)i Fn(the)e(option)g Fl(--enable-gmp)j +Fn(y)m(ou)d(ask)g(for)f(GMP)501 1739 y(v)m(ersion)34 +b(only)-8 b(.)403 1943 y Fm(\017)48 b Fn(By)43 b(default,)h(PIP)f(lo)s +(oks)f(for)f(the)h(GMP)h(library)f(in)g(the)g(standard)g(path)g(\()p +Fl(/usr/)501 2063 y Fn(or)34 b Fl(/usr/local/)p Fn(\).)50 b(If)34 b(the)g(m)m(ultiple)i(precision)f(Pip)f(construction)i(is)e -(needed)h(and)501 814 y(if)47 b(the)h(GMP)f(library)h(w)m(as)g +(needed)h(and)501 2183 y(if)47 b(the)h(GMP)f(library)h(w)m(as)g (installed)h(elsewhere,)k(y)m(ou)48 b(m)m(ust)h(m)m(ust)f(giv)m(e)g(to) -f(the)501 934 y Fl(configure)k Fn(shell)e(script)g(the)g(option)f +f(the)501 2304 y Fl(configure)k Fn(shell)e(script)g(the)g(option)f Fl(--with-gmp=PATH)p Fn(,)k(where)d Fl(PATH)g Fn(is)g(the)501 -1054 y(GMP)d(library)h(installation)f(path.)83 b(Another)47 +2424 y(GMP)d(library)h(installation)f(path.)83 b(Another)47 b(p)s(ossibilit)m(y)g(is)g(to)e(giv)m(e)i(the)f(GMP)501 -1175 y(include)26 b(and/or)e(library)g(path)h(separately)g(b)m(y)h -(using)e Fl(--with-gmp-include=PATH)501 1295 y Fn(and)33 -b Fl(--with-gmp-library=PATH)p Fn(.)257 1555 y Fg(4.4.3)113 -b(uninstallation)257 1740 y Fn(Y)-8 b(ou)44 b(can)g(easily)h(remo)m(v)m +2545 y(include)26 b(and/or)e(library)g(path)h(separately)g(b)m(y)h +(using)e Fl(--with-gmp-include=PATH)501 2665 y Fn(and)33 +b Fl(--with-gmp-library=PATH)p Fn(.)257 2925 y Fg(4.4.3)113 +b(uninstallation)257 3110 y Fn(Y)-8 b(ou)44 b(can)g(easily)h(remo)m(v)m (e)g(PIP)f(and)g(the)g(PipLib)g(from)g(y)m(our)g(system)i(b)m(y)e(t)m -(yping)g Fl(make)257 1860 y(uninstall)p Fn(.)404 2099 +(yping)g Fl(make)257 3230 y(uninstall)p Fn(.)404 3468 y(Rep)s(ort)32 b(all)g(bugs,)i(problems,)g(inaccuracies)g(in)f(the)g -(do)s(cumen)m(tation)g(to:)404 2219 y Fl(Paul.Feautrier@ens-lyon.fr)404 -2339 y(Cedric.Bastoul@prism.uvsq.)q(fr)404 2460 y Fn(Praise)g(is)g -(also)g(appreciated.)404 2580 y(Let)f(the)h(p)s(o)m(w)m(er)h(of)e +(do)s(cumen)m(tation)g(to:)404 3589 y Fl(Paul.Feautrier@ens-lyon.fr)404 +3709 y(Cedric.Bastoul@prism.uvsq.)q(fr)404 3830 y Fn(Praise)g(is)g +(also)g(appreciated.)404 3950 y(Let)f(the)h(p)s(o)m(w)m(er)h(of)e (parametric)h(in)m(teger)h(programming)e(b)s(e)h(with)g(y)m(ou.)257 -2913 y Fo(References)257 3132 y Fn([1])49 b(P)m(aul)68 +4283 y Fo(References)257 4502 y Fn([1])49 b(P)m(aul)68 b(F)-8 b(eautrier.)148 b(P)m(arametric)69 b(in)m(teger)f(programming.) -148 b Fi(RAIR)n(O)67 b(R)-5 b(e)g(cher)g(che)409 3252 +148 b Fi(RAIR)n(O)67 b(R)-5 b(e)g(cher)g(che)409 4622 y(Op)n(\023)-47 b(er)-5 b(ationnel)5 b(le)p Fn(,)30 b(22:243{268,)h -(Septem)m(b)s(er)j(1988.)257 3456 y([2])49 b(P)m(aul)h(F)-8 +(Septem)m(b)s(er)j(1988.)257 4826 y([2])49 b(P)m(aul)h(F)-8 b(eautrier.)95 b(Seman)m(tical)51 b(analysis)g(and)e(mathematical)i -(programming;)58 b(ap-)409 3576 y(plication)48 b(to)g(parallelization)g +(programming;)58 b(ap-)409 4946 y(plication)48 b(to)g(parallelization)g (and)g(v)m(ectorization.)91 b(In)48 b(M.)g(Cosnard,)53 -b(Y.)48 b(Rob)s(ert,)409 3696 y(P)-8 b(.)41 b(Quin)m(ton,)j(and)d(M.)h +b(Y.)48 b(Rob)s(ert,)409 5066 y(P)-8 b(.)41 b(Quin)m(ton,)j(and)d(M.)h (Ra)m(ynal,)h(editors,)h Fi(Workshop)e(on)h(Par)-5 b(al)5 -b(lel)42 b(and)g(Distribute)-5 b(d)409 3817 y(A)n(lgorithms,)34 +b(lel)42 b(and)g(Distribute)-5 b(d)409 5187 y(A)n(lgorithms,)34 b(Bonas)p Fn(,)e(pages)h(309{320.)e(North)h(Holland,)h(1989.)257 -4020 y([3])49 b(Doran)28 b(K.)h(Wilde.)38 b(A)28 b(library)i(for)e +5390 y([3])49 b(Doran)28 b(K.)h(Wilde.)38 b(A)28 b(library)i(for)e (doing)g(p)s(olyhedral)i(op)s(erations.)37 b(T)-8 b(ec)m(hnical)31 -b(Rep)s(ort)409 4141 y(785,)h(IRISA,)h(Rennes,)h(F)-8 +b(Rep)s(ort)409 5510 y(785,)h(IRISA,)h(Rennes,)h(F)-8 b(rance,)33 b(1993.)p eop end %%Trailer diff --git a/doc/source/images/negatifs.eps b/doc/source/images/negatifs.eps new file mode 100644 index 0000000..b7ac6fb --- /dev/null +++ b/doc/source/images/negatifs.eps @@ -0,0 +1,110 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Title: /tmp/xfig-fig001441 +%%Creator: fig2dev Version 2.1.8 Patchlevel 0 +%%CreationDate: Thu May 9 15:32:56 1996 +%%For: jfcollar@monet (Jean-Francois COLLARD) +%%Orientation: Portrait +%%BoundingBox: 0 0 362 273 +%%Pages: 0 +%%EndComments +/$F2psDict 200 dict def +$F2psDict begin +$F2psDict /mtrx matrix put +/l {lineto} bind def +/m {moveto} bind def +/s {stroke} bind def +/n {newpath} bind def +/gs {gsave} bind def +/gr {grestore} bind def +/clp {closepath} bind def +/graycol {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul +4 -2 roll mul setrgbcolor} bind def +/col-1 {} def +/col0 {0 0 0 setrgbcolor} bind def +/col1 {0 0 1 setrgbcolor} bind def +/col2 {0 1 0 setrgbcolor} bind def +/col3 {0 1 1 setrgbcolor} bind def +/col4 {1 0 0 setrgbcolor} bind def +/col5 {1 0 1 setrgbcolor} bind def +/col6 {1 1 0 setrgbcolor} bind def +/col7 {1 1 1 setrgbcolor} bind def +/col8 {.68 .85 .9 setrgbcolor} bind def +/col9 {0 .39 0 setrgbcolor} bind def +/col10 {.65 .17 .17 setrgbcolor} bind def +/col11 {1 .51 0 setrgbcolor} bind def +/col12 {.63 .13 .94 setrgbcolor} bind def +/col13 {1 .75 .8 setrgbcolor} bind def +/col14 {.7 .13 .13 setrgbcolor} bind def +/col15 {1 .84 0 setrgbcolor} bind def + /DrawEllipse { + /endangle exch def + /startangle exch def + /yrad exch def + /xrad exch def + /y exch def + /x exch def + /savematrix mtrx currentmatrix def + x y translate xrad yrad scale 0 0 1 startangle endangle arc + savematrix setmatrix + } def + + end +/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def +/$F2psEnd {$F2psEnteredState restore end} def +%%EndProlog + +$F2psBegin +0 setlinecap 0 setlinejoin +-94.0 513.0 translate 0.900 -0.900 scale +0.500 setlinewidth +% Ellipse +n 374 389 2 2 0 360 DrawEllipse gs 0.00 setgray fill gr +gs col0 s gr +% Ellipse +n 314 329 2 2 0 360 DrawEllipse gs 0.00 setgray fill gr +gs col0 s gr +% Ellipse +n 314 509 2 2 0 360 DrawEllipse gs 0.00 setgray fill gr +gs col0 s gr +% Ellipse +n 314 449 2 2 0 360 DrawEllipse gs 0.00 setgray fill gr +gs col0 s gr +% Ellipse +n 134 389 2 2 0 360 DrawEllipse gs 0.00 setgray fill gr +gs col0 s gr +% Ellipse +n 194 389 2 2 0 360 DrawEllipse gs 0.00 setgray fill gr +gs col0 s gr +% Ellipse +n 254 389 2 2 0 360 DrawEllipse gs 0.00 setgray fill gr +gs col0 s gr +% Polyline +n 104 389 m 506 389 l gs col-1 s gr +n 498.000 387.000 m 506.000 389.000 l 498.000 391.000 l gs 2 setlinejoin col-1 s gr +% Polyline +n 314 569 m 314 281 l gs col-1 s gr +n 312.000 289.000 m 314.000 281.000 l 316.000 289.000 l gs 2 setlinejoin col-1 s gr +% Polyline +n 254 329 m 134 449 l 254 569 l 374 449 l 254 329 l gs col-1 s gr +% Polyline +n 314 554 m 314 266 l gs col-1 s gr +n 312.000 274.000 m 314.000 266.000 l 316.000 274.000 l gs 2 setlinejoin col-1 s gr +/Times-Italic findfont 18.00 scalefont setfont +479 374 m +gs 1 -1 scale (i) col-1 show gr +/Times-Italic findfont 18.00 scalefont setfont +299 299 m +gs 1 -1 scale (j) col-1 show gr +/Times-Italic findfont 18.00 scalefont setfont +231 407 m +gs 1 -1 scale (-n-5) col-1 show gr +/Times-Italic findfont 18.00 scalefont setfont +358 405 m +gs 1 -1 scale (n+5) col-1 show gr +/Times-Italic findfont 18.00 scalefont setfont +320 454 m +gs 1 -1 scale (-n-5) col-1 show gr +/Times-Italic findfont 18.00 scalefont setfont +322 333 m +gs 1 -1 scale (n+5) col-1 show gr +$F2psEnd diff --git a/doc/source/images/negatifs.fig b/doc/source/images/negatifs.fig new file mode 100644 index 0000000..cb4b5de --- /dev/null +++ b/doc/source/images/negatifs.fig @@ -0,0 +1,26 @@ +#FIG 2.1 +80 2 +1 4 0 1 0 0 0 21 0.00000 1 0.000 374 389 2 2 372 388 376 390 +1 4 0 1 0 0 0 21 0.00000 1 0.000 314 329 2 2 312 328 316 330 +1 4 0 1 0 0 0 21 0.00000 1 0.000 314 509 2 2 312 508 316 510 +1 4 0 1 0 0 0 21 0.00000 1 0.000 314 449 2 2 312 448 316 450 +1 4 0 1 0 0 0 21 0.00000 1 0.000 134 389 2 2 132 388 136 390 +1 4 0 1 0 0 0 21 0.00000 1 0.000 194 389 2 2 192 388 196 390 +1 4 0 1 0 0 0 21 0.00000 1 0.000 254 389 2 2 252 388 256 390 +2 1 0 1 -1 0 0 0 0.000 -1 1 0 + 0 0 1.000 4.000 8.000 + 104 389 506 389 9999 9999 +2 1 0 1 -1 0 0 0 0.000 -1 1 0 + 0 0 1.000 4.000 8.000 + 314 569 314 281 9999 9999 +2 1 0 1 -1 0 0 0 0.000 -1 0 0 + 254 329 134 449 254 569 374 449 254 329 9999 9999 +2 1 0 1 -1 0 0 0 0.000 -1 1 0 + 0 0 1.000 4.000 8.000 + 314 554 314 266 9999 9999 +4 0 3 18 0 -1 0 0.00000 2 22 5 479 374 i +4 0 3 18 0 -1 0 0.00000 2 22 5 299 299 j +4 0 3 18 0 -1 0 0.00000 2 22 41 231 407 -n-5 +4 0 3 18 0 -1 0 0.00000 2 22 32 358 405 n+5 +4 0 3 18 0 -1 0 0.00000 2 22 41 320 454 -n-5 +4 0 3 18 0 -1 0 0.00000 2 22 32 322 333 n+5 diff --git a/doc/source/makefile b/doc/source/makefile new file mode 100644 index 0000000..6415f1f --- /dev/null +++ b/doc/source/makefile @@ -0,0 +1,23 @@ +NAME_SOURCE=pip +NAME=pip + +all: + latex $(NAME_SOURCE).tex + latex $(NAME_SOURCE).tex + dvips -o $(NAME).ps $(NAME_SOURCE).dvi +clean: + rm -f $(NAME).aux $(NAME).log $(NAME).dvi + +html: + latex2html -t PipLib -white -address cedric.bastoul@inria.fr \ + -show_section_numbers \ + -antialias -split 4 -info 0 -html_version 3.2,math pip.tex + +cleanall: clean + rm -f $(NAME).ps + +tgz: cleanall + (cd .. && \ + tar cvf piplib-doc.tar piplib-doc && \ + gzip piplib-doc.tar) + diff --git a/doc/source/pip.bbl b/doc/source/pip.bbl new file mode 100644 index 0000000..82965d6 --- /dev/null +++ b/doc/source/pip.bbl @@ -0,0 +1,22 @@ +\begin{thebibliography}{1} + +\bibitem{Feau:88b} +Paul Feautrier. +\newblock Parametric integer programming. +\newblock {\em RAIRO Recherche Op\'{e}rationnelle}, 22:243--268, September + 1988. + +\bibitem{Feau:88c} +Paul Feautrier. +\newblock Semantical analysis and mathematical programming; application to + parallelization and vectorization. +\newblock In M.~Cosnard, Y.~Robert, P.~Quinton, and M.~Raynal, editors, {\em + Workshop on Parallel and Distributed Algorithms, Bonas}, pages 309--320. + North Holland, 1989. + +\bibitem{Wild:93} +Doran K. Wilde. +\newblock A library for doing polyhedral operations. +\newblock Technical Report 785, IRISA, Rennes, France, 1993. + +\end{thebibliography} diff --git a/doc/source/pip.tex b/doc/source/pip.tex new file mode 100644 index 0000000..4f4a2f0 --- /dev/null +++ b/doc/source/pip.tex @@ -0,0 +1,1257 @@ +\documentclass[12pt,a4paper]{article} +\usepackage{graphicx,html} + +\htmladdtonavigation{\htmladdnormallink +{\htmladdimg{../images/home.png}}{../piplib.html}} + +% NdCed: ca c'est pour retrouver le format original (le document de 96 +% etait prevu pour LaTeX 2.09, et est a present au standard LaTeX2e). +\setlength{\textwidth}{145mm} +\setlength{\textheight}{219mm} + +\newcommand{\pair}[2]{\,<\!#1,#2\!>\,} +\newcommand{\bq}{\begin{equation}} +\newcommand{\eq}{\end{equation}} +\newenvironment{exemple}{\begin{quote} \small}{\end{quote}} +\newtheorem{grammar}{Grammar} +\def\|#1|{\mathrel{\hbox{\tt #1}}} + +\date{Additions by Jean-Fran\c{c}ois Collard and C\'edric Bastoul\\ +Fourth Version, rev 1.5, November 8, 2005} + +\title{Solving Systems of Affine (In)Equalities: PIP's User's Guide} + +\author{Paul Feautrier} + +\begin{document} + +\pagestyle{headings} + +\maketitle +\bibliographystyle{plain} + +\begin{abstract} +This document is the User's Manual of PIP, a software which solves +Parametric Integer Programming problems. That is, PIP finds the +lexicographic minimum of the set of integer points which lie inside a +convex polyhedron, when that polyhedron depends linearly on one or +more integral parameters. +\end{abstract} + +\section{Introduction} +The semantic analysis of programs accessing arrays often boils down +to finding integer solutions to parametric linear programming problems. This is +due to two main phenomena: +\begin{itemize} +\item Array subscripts are very often linear functions of surrounding loop counters~; +\item The program's execution order enforces an order on possible solutions. +\end{itemize} + +Let us consider the following example: +\begin{verbatim} + for i:= 0 to m do + for j := 0 to n do {I} + a[2*i+j] := i+j; +\end{verbatim} + +After completion of execution, for which values of $k$ is {\tt A[}$k${\tt ]} +defined, and which instances of the assignment wrote into +this array element? We can easily check that answering this question +is equivalent to finding the solutions of the following system, where $i, +j$ and $k$ are the unknowns: +\begin{eqnarray} +0 \leq & i & \leq m ,\\ +0 \leq & j & \leq n ,\\ +2i + j & = & k . +\end{eqnarray} + +Moreover, if we want to know which instance gave its {\em final} value +to {\tt A[}$k${\tt ]}, that is if we are looking for the {\em last} instance +writing into {\tt A[}$k${\tt ]}, then we have to look for the maximal value +of vector $(i,j)$ according to lexicographic order. We +thus consider the following {\em polyhedron} ${\cal F}(k, m, n) $: +\begin{equation} +{\cal F}(k, m, n) = \{| 0 \leq i \leq m, 0 \leq j \leq n, 2i+j = k\} . +\label{exp1} +\end{equation} +What is the lexicographical maximum of the +integer-valued vectors included in ${\cal F}(k, m, n)$? +The aim of PIP is to solve such problems. The reader is refered to +\cite{Feau:88b} for a mathematical description of the method. +% +% Ajouter qq explications +% + + +\subsection{General formulation} +Let ${\cal F}$ be a polyhedron: +\begin{equation} + \label{polyedre} +{\cal F}(\vec{z}) + = \{ \vec{x} | \vec{x} \geq 0, + {\bf A} \vec{x} + {\bf B} \vec{z} + \vec{c} \geq 0\} . +\end{equation} +In this formula, $\vec{x}$ is a vector with $n$ entries: the vector of +all unknowns. $\vec{z}$, $\vec{z}\geq 0$, is the vector built from +parameters and has $p$ entries. Polyhedron ${\cal F}(\vec{z})$ is a +subset of ${\bf R}^{n}$ and is defined by $n + l$ inequalities: $n$ +inequalities expressing +\[ \vec{x} \geq 0 \] +and the $l$ inequalities correponding to rows of matrix +${\bf A}$ of size $l \times n$, matrix ${\bf B}$ of size $l \times p$, +and constant vector $\vec{c}$ of size $l$. + +Size parameters can themselves be constrained by a set of affine inequalities +\[ {\bf M} \vec{z} + \vec{h} \geq 0 ,\] +which is called the {\em context} of the problem. ${\bf M}$ is an $m +\times p$ matrix and $\vec{h}$ a vector of dimension $m$. +All data of a PIP problem: (${\bf A}, {\bf B}, {\bf M}, \vec{c}, \vec{h}$) + are assumed to be integer-valued. + + +\section{Using the PIP Software} +\label{PIP} + +\subsection{Writing the Input File} +\label{specif:donnees} + +The input text file follows the following context-free grammar: +\begin{grammar} +: +\label{probleme} +\begin{verbatim} +File ::= Problem ... +Problem ::= ( Comments Nn Np Nl Nm Bg Nq Tableau Context ) +Comments ::= List +List ::= Atom | ( List ... ) +Tableau ::= ( Vector ... ) +Context ::= ( Vector ... ) +Vector ::= #[ Integer ... ] +Nn ::= Integer +Np ::= Integer +Nl ::= Integer +Nm ::= Integer +Bg ::= Integer +Nq ::= 0 | 1 +\end{verbatim} +\end{grammar} +This syntax was chosen so as to ease the generation of problems + by a Lisp program. In +particular, each {\tt Problem} is a balanced list, as far as both +parentheses and brackets are concerned. + +\begin{itemize} +\item +{\tt Comments} are arbitrary lists. These comments are +written verbatim to the output file, and are useful to keep track of +problems and solutions. + +Note that several {\tt Problem}s can be given to PIP in the same +file. The problems may be separated by any text that does not +contain a parenthesis. By using Unix FIFO's as input and output files, +it is easy to convert the present implementation of PIP into a +linear programming server. + +\item +{\tt Nn} is the number of unknowns in the program (which was denoted +by $n$ in the first section). + +\item {\tt Np} is the number of (symbolic) parameters ($p$) + +\item {\tt Nl} is the number of inequalities defining the domain of the unknowns ($l$). + +\item {\tt Nm} is the number of inequalities satisfied by the parameters ($m$). + +\item {\tt Bg} is the index of a ``Big'' parameter whose value is assumed +to be infinitely large. That is, if the big parameter appears with a +positive coefficient in a form $\phi$, then we can immediately deduce +that $\phi > 0$. If {\tt Bg} is set to a nonpositive +value, then there is no big parameter in the problem to be solved. + +Be aware that {\tt Bg} is the column rank of the corresponding +parameter in the {\tt Tableau}, and that the first valid value for it +is {\tt Nn+1}. + +\item {\tt Nq} is an integer but should be interpreted + as a boolean value {\sl \`a la} +C, that is, it denotes ``true'' if its value is nonzero. If {\tt Nq} +is true, then an integer-valued solution is looked for. Otherwise, PIP +finds the lexicographic minimum rational solution to the problem. + +\item {\tt Tableau} stores the set of inequalities defining the domain +of unknowns. Each {\tt Vector} represents one inequality. The entries +in {\tt Vector} are, in this order: +\begin{itemize} +\item the coefficients of the unknowns (I.e., a row of matrix ${\bf A}$), +\item the (additive) constant, (I.e., an entry of vector $\vec{c}$), +\item the coefficients of the parameters (I.e., a row of matrix ${\bf B}$) +\end{itemize} +This notation heavily depends on the positions given +to unknowns and parameters: it is the responsability of the user to +enforce a coherent ordering of coefficients and to set a coefficient +to zero when the corresponding unknown/parameter does not appear. + +There are $l$ such {\tt Vector}s in {\tt Tableau}, and each {\tt +vector} exactly has $n+1+p$ entries. + + +\item In a similar way, {\tt Context} is a list of {\tt Vector}s. Each {\tt Vector} represents a row of Matrix ${\bf M}$ followed by the +corresponding entry in vector $\vec{h}$. {\tt Context} thus includes +$m$ {\tt Vector}s of $p + 1$ entries. + +\end{itemize} + + + +\subsubsection{Example} \label{exp2} +This example is taken from \cite{Feau:88c}. We consider the loop nest below: +\begin{verbatim} +for i:= 0 to m do + for j := 0 to n do {II} + for k := 0 to i+j do ... +\end{verbatim} +and we wish to rewrite this nest in the order {\tt k, j, i}. The +bounds on {\tt k} can easily be guessed ($0\leq k \leq m+n$), so let's +look for the lower bound on {\tt j} in the rewritten nest. This lower bound on +{\tt j} can be found by solving the following problem: +\[ {\cal D}_{2}(k) = \{\pair{j}{i} | i \leq m, j \leq n, k \leq i + j\} .\] + +This problem is to be solved in the context $k \leq m+n$. The input file +may thus look like this: +\begin{verbatim} +( (Lower bound on j after loop inversion + (unknowns j i) + (parameters k m n)) + 2 3 3 1 -1 1 + ( #[0 -1 0 0 1 0] + #[-1 0 0 0 0 1] + #[1 1 0 -1 0 0] + ) + ( #[-1 1 1 0]) +) +\end{verbatim} +The first sequence of integers should be read as: This problem has 2 +unknowns ($i$ and $j$) and 3 parameters ($k$, $m$ and $n$). The domain is +defined by 3 inequalities, the context by 1 inequality. There is no +(-1) big parameter and it is true (1) that we are looking for an +integer solution. + +\subsection{Calling PIP} +PIP is called by the following command: +\begin{verbatim} + pip [-s|-v...] [-d] [-z] [input [output]] +\end{verbatim} +PIP prints some information on the screen after having solved a +problem. The {\tt -s} (silent mode) switches this feature off. On the +contrary, the verbose {\tt -v} option tells PIP to copy, in a file, +all the input data and all the intermediary results. The name of this +file is given either by the variable {\tt DEBUG} in the environment or +is built by {\tt mkstemp}. The number of consecutive vee's controls the +degree of verbosity of Pip. A word of caution: debug files may become +very large very fast. + +When Pip is asked for an integral solution, it constructs new constraints +(the so-called {\em cuts}) which eliminate fractional solutions and keep +all integer solutions. The selection of cuts is somewhat arbitrary. When +the {\tt -d} option is given, Pip uses this degree of freedom to select +the ``deepest cut'' according to an algorithm by Gondran. Untractable +problems may become tractable when using this option, and conversely. +Use with caution. + +If the {\tt -z} option is given, then the solution is somewhat simplified +(see below). + +{\tt input} and {\tt output} are the names of the input (data) and +output (results) files, respectively. If no {\tt output} ({\tt +input}) file is given, then the results are printed to the standard +output (input). + + +\subsubsection{Messages} +\begin{itemize} + +\item {\tt Version X.x}. Currently, {\tt D.1}. + +\item {\tt cross : , alloc : } This message is output after solving + each problem. The value of {\tt } gives an idea of the complexity of + the problem. +\end{itemize} + +\paragraph{Errors related to the input} +\begin{itemize} +\item {\tt Syntax error}: unbalanced parentheses in the input. + +\item {\tt Your computer doesn't have enough memory}: self explanatory. +\end{itemize} +\paragraph{Errors related to the solution} +\begin{itemize} +\item {\tt Integer Overflow}: A number has been generated that is too large +to be accommodated in a 32 bit integer. Check the input and/or switch +to Zbigniew Chamski's infinite precision PIP. + +\item {\tt The solution is too complex}: the solution quast has grown beyond +the memory allocated to it. Check the input and/or change the value of +constant {\tt SOL\_SIZE} in file {\tt type.h}, then rebuild PIP. + +\item {\tt Memory overflow}: self explanatory. + +\item {\tt unaccessible}: one of the input, output or debug file +cannot be opened. +\end{itemize} +\paragraph{Dimension errors} +\begin{itemize} +\item {\tt Too much variables} + +\item {\tt Too much parameters} : Check the input and/or change the value of +constants {\tt MAXCOL} and {\tt MAXPARM} in file {\tt type.h}, then +rebuild PIP. +\end{itemize} +\paragraph{Implementation errors} + +All such error messages begin by the word {\tt Syserr}. These messages +indicate a bug in the implementation. You should report such events +by sending a copy of the input file by e-mail to the author, \linebreak +{\tt Paul.Feautrier@prism.uvsq.fr} who will endeavor to solve the problem +as soon as possible. + +\subsection{Output Data}\label{OutputData} +The output file can be described by the following grammar: +\begin{grammar}\label{GrammarOutputData} +: +\label{resultat} +\begin{verbatim} +File ::= Result ... +Result :: ( Comments Solution ) +Solution ::= Quast_group + | void +Quast_group ::= Quast + | Newparm ... Quast +Quast ::= Form + | (if Vector Quast_group Quast_group) +Form ::= (list Vector ...) + | nil +Newparm ::= (newparm Integer (div Vector Integer)) +Vector ::= #[ Coefficient ... ] +Coefficient ::= Integer | Integer / Integer +\end{verbatim} +\end{grammar} +The {\tt Comments} are copied from the input file. The {\tt Solution} +is said to be {\tt void} when the initial context is void. Otherwise, +it is given as a quast written {\sl \`a la} Lisp. The quast may +possibly be preceded by the definition of one or several new +parameters. + +The vector coefficients may be either integers or rationals written as +{\tt num/denom}. The latter case occurs if {\tt Nq} had been +set to 0 in the input file. + +In the solution, a {\tt Vector} represents an affine form; each entry +is the coefficient of the corresponding parameter (the parameter of +the same rank). The last entry is the additive constant. + +The definition of a new parameter begins with the key-word +{\tt newparm}, then a rank number, a vector of coefficients, and a +denominator. The new parameter is equal to the integer division of the +vector by the denominator. The new parameter can only appear in the +{\tt Quast} following its definition. Introducing a new parameter adds +one entry in the list of parameters, so the length of vectors in the +solution is not constant. However, this length is always equal to 1 plus +the number of original parameters plus the number of new parameters +currently defined. + +The solution is a multi-level conditional expression (a +tree of nested conditionals.) A predicate expression $p$ should be +understood as the boolean expression $p\geq 0$. Leaves of the +conditional tree are either {\tt nil}, meaning that the input problem +has no solution, or a {\tt Form}. A {\tt Form} is a list of vectors, +each vector giving the value of the corresponding unknown. + +\subsubsection{Example} +The output of PIP is not intended for human consumption. +No attempt has been made to implement a pretty-printer. In the interest +of readability, some of the result files in this paper have been beautified +by hand. The reader should not be surprised if he gets results with +different layouts when running the examples. + +Here is the output solution file for the example above (\ref{exp2}): +\begin{verbatim} +( (Lower bound on j after loop inversion + (unknowns j i) + (parameters k m n) 1 )(if #[ -1 1 0 0] +(list #[ 0 0 0 0] +#[ 1 0 0 0] +) +(list #[ 1 -1 0 0] +#[ 0 1 0 0] +) +) +) +\end{verbatim} +To express this solution, no new parameter had to be introduced. The +form associated to the first conditional is: +\[ -1 \times k + 1 \times m + 0 \times n + 0 \times 1 = m-k \] +so the test should be read as $k - m \geq 0$. If this inequality +holds, then the solution is $<0, k>$. Otherwise, the solution is +$$. + +To sum things up, the lexicographical minimum of ${\cal D}_2$ is: +\begin{verbatim} + if m-k >= 0 then <0, k> else . +\end{verbatim} +Hence the lower bound on the first coordinate: +\begin{verbatim} + if m-k >= 0 then 0 else k-m +\end{verbatim} + +\subsubsection{Simplifying the solution} + +The solution of a parametric problem may be in the form of a quast all +of whose leaves are nil. This means in fact that the original polyhedron +is empty whatever the values of the parameters. An example, due to Dirk +Fimmel, is the following: + +\begin{verbatim} +(((i j 1)(m n)) + 2 2 7 0 -1 1 + (#[2 6 -9 0 0] + #[5 -3 0 0 0] + #[2 -10 15 0 0] + #[-2 6 -3 0 0] + #[-2 -6 17 0 0] + #[0 1 0 -1 0] + #[1 0 0 0 -1] + ) + () +) +\end{verbatim} +Without the {\tt -z} option, the solution is: +\begin{verbatim} +(((i j 1)(m n) -1 ) + (if #[ -4 0 5] + (if #[ 0 -4 3] + () + (if #[ 0 -2 9] + (if #[ 0 -2 3] + (newparm 2 (div #[ 0 2 3] 6)) + (newparm 3 (div #[ 0 2 10 7] 12)) + (newparm 4 (div #[ 0 4 0 2 1] 6)) + () + (if #[ 0 -2 7] + (newparm 2 (div #[ 0 4 3] 6)) + (if #[ 0 -8 6 11] () ()) + ())) + ())) + (if #[ -1 0 3] + (if #[ -1 0 2] + (if #[ 10 -2 -15] ()()) + ()) + ())) +) +\end{verbatim} +Inspection reveals that all leaves are {\tt ()}. With the {\tt -z} option, +the solution is much simpler: +\begin{verbatim} +(((i j 1)(m n) -1 )() +) +\end{verbatim} +\subsection{The Power of PIP} +In the following sections, we explain how PIP can be used to solve +extended classes of problems: +\begin{itemize} +\item Problems where equalities occur. +\item Problems where a lexicographical {\em maximum} has to +be found. +\item Cases when linear cost functions are to be optimized. +\item Problems where unknowns and/or parameters may be negative +\end{itemize} + +\subsubsection{Handling Equalities} +When the input problem contains $r$ affine equalities $f_i = 0$,$1\leq i\leq r$, + one may just write $r$ inequalities $f_i \geq 0$ and $r$ inequalties $f_i \leq 0$, + thus satisfying PIP's input syntax. However, one may notice that only $r+1$ inequalities +are needed: $f_i \geq 0$, $1\leq i\leq r$, and the following inequality: +\[ \sum_{i=1}^{r} f_i \leq 0.\] + +\subsubsection{The bigparm trick} + +In some cases, it is useful to suppose that one parameter in a PIP problem +grows ``very large''. Some examples will be given in the following sections. +Let $B$ be the name of this parameter. Suppose that in the solution, one +of the predicates is: +\[ a B + b \ge 0 ,\] +where $b$ may depend on all other parameters. For $B$ large enough, if $a > 0$ +then the predicate is true, and if $a < 0$ then the predicate is false. +One can find the limit shape of the solution by removing such tests and +replacing them by their true of false branch, as appropriate. This can be done +{\sl a posteriori\/} on the results of PIP, or PIP can do it ``on the fly'' +while solving the problem. This last method is more efficient, since it +tends to simplify the solution. + +PIP is notified of the presence of a big parameter by setting the {\tt Bg} +argument to a positive value. This value is the rank of the big parameter +in the problem tableau. Hence, the lowest admissible value for {\tt Bg} +is {\tt Nn + 1}. + +The reader should convince himself that in the presence of two big +parameters, no such simplifications are possible unless one has some +information on the relative size of the parameters. Such situations +should be handled by giving PIP ordinary parameters, and doing the +simplification on the solution in the light of extra knowledge. + +\subsubsection{Computing Lexicographical Maxima} +\label{maximum} +To get the maximum of an unknown $x$, minimize $B - x$, where +B is a new "big" parameter. Adding a parameter just adds one column +in the problem tableau. The fact that this column corresponds to a Big +parameter is specified by setting the 5-th switch to a positive value, +this value being the position of the column of B in the problem +tableau. + +These cases can be handled systematically in the following way. Suppose that +we are asked for the integer maximum of the polyhedron: +\begin{eqnarray} +x & \ge & 0, \nonumber \\ +y & \ge & 0, \label{biggy}\\ +3 y & \le & x + 12, \nonumber\\ +y & \ge & 2 x - 3. \nonumber +\end{eqnarray} +Let us introduce the new unknowns: +\[ x'= B - x, \;\; y' = B - y ,\] +where $B$ is the big parameter. System (\ref{biggy}) translates to: +\begin{eqnarray*} +-x' + B & \ge & 0,\\ +-y' + B & \ge & 0,\\ +-x' + 3y' + 12 - 2B & \ge & 0,\\ +2x' - y' + 3 - B & \ge & 0. +\end{eqnarray*} +Finding the maximum of $(x,y)^T$ is equivalent to finding the minimum of +$(x', y')^T$, provided $B$ is large enough. The solution of the above +problem is: +\begin{verbatim} +((a maximization problem 1 ) + (if #[ -1 6] + (if #[ -1 3] + (list #[ 0 0] + #[ 0 0]) + (if #[ -5 27] + (newparm 1 (div #[ 1 1] 2)) + (list #[ 1 -1 -1] + #[ 0 0 0]) + (list #[ 1 -4] + #[ 1 -5]))) + (list #[ 1 -4] + #[ 1 -5]))) +\end{verbatim} + +Suppose we tell PIP that $B$ is a large parameter. The input file is +now: +\begin{verbatim} +((a maximization problem) + 2 1 4 0 3 1 + (#[-1 0 0 1] + #[0 -1 0 1] + #[-1 3 12 -2] + #[2 -1 3 -1] + ) + () +) +\end{verbatim} +and the solution is much simpler: +\begin{verbatim} +((a maximization problem 1 ) + (list #[ 1 -4] + #[ 1 -5])) +\end{verbatim} +The reader may care to check that this result is equivalent to the +previous one as soon as $B > 5$. The position of the minimum is: +$x' = B - 4, y' = B - 5$, from which we deduce: $x = 4, y = 5$. As +expected, $B$ has disappeared from the solution. If this does not happen, +we observe first that $B$ must have a positive coefficient in the result +(if not, one of the inequalities $x, y \ge 0$ would be violated for $B$ +large enough). This means that the original polyhedron is not bounded, +since, whatever $B$, it contains a point whose coordinates are $O(B)$, +and hence has no maximum. + +\subsubsection{Optimizing Linear Cost Functions} + +The problem here is to compute the minimum of a linear function $cx$ +in a polyhedron $P$, +where $c$ is a vector with integer coefficients. Let us introduce +a new unknown $y$. Solve the linear programming problem obtained by +adding the constraint $y \ge cx$ to the defining constraints of $P$. +$y$ should be the first unknown in the lexicographic ordering. Let +$y_s, x_s$ be the solution. Suppose that the minimum of $cx$ in $P$ +is obtained at $x_m$ and set $y_m = c x_m$. Since $x_s$ is in $P$, +and $y_s \ge cx_s$, it is clear that $y_s \ge y_m$. Conversely, +$(y_m, x_m)$ satisfies the constraints of the problem of which $(y_s, x_m)$ +is the lexicographic minimum. Hence $(y_s, x_s) \ll (y_m, x_m)$, and, +since $y$ is the first unknown, $y_s \le y_m$. Hence, $y_m = y_s$. +There is no guarantee, however, that $x_s = x_m$. + +% +% an example needed here +% + + +\subsubsection{Negative Unknowns and Parameters} + +Suppose we want to find the minimum of $f(i,j) = i-2j$ over the square +domain represented in Figure~\ref{iter-domain}% +\footnote{This example was proposed and solved by Pierre Boulet.}. + +\begin{figure}[htb] +\hrule width \columnwidth +\centering\leavevmode +\includegraphics[height=6.5cm]{images/negatifs.eps} +\caption{\label{iter-domain} Problem domain} +\end{figure} + +As above, +we introduce a new unknown $f$ and the inequality $f-i+2j \geq +0$. Since we want to optimize $f$, $f$ will appear +as the first unknown. + +The trick for solving the problem in $Z$ is to introduce the following +parameters: +\begin{itemize} +\item $G \ge max(0, -i, -j, -f)$. +\item $P = max(0, -n)$. +\end{itemize} +This choice insure that the new variables and parameters: +\begin{eqnarray*} +f' &=& G + f \\ +i' &=& G + i \\ +j' &=& G + j \\ +n' &=& P + n +\end{eqnarray*} +are all positive. This property stays true if $G$ grows. Hence, $G$ +is again a big parameter. However, $P$ must be considered as an ordinary +parameter. After replacement of $i,j,n, f$ by the new variables +$i',j',n',f'$, we get a system which corresponds to the following input: + +\begin{verbatim} +( + ( Solving MIN(i-2.j) under the following constraints: + Unknowns may be negative. + Order: + f' i' j' constant G P n' + ) + 3 3 5 0 4 1 + ( + #[ 0 1 1 20 -2 -4 4 ] + #[ 1 -1 2 0 -2 0 0 ] + #[ 0 -1 -1 0 2 0 0 ] + #[ 0 1 -1 10 0 -2 2 ] + #[ 0 -1 1 10 0 -2 2 ] + ) + ( )) +\end{verbatim} + +The result is: +\begin{verbatim} +( + ( Solving MIN(i-2.j) under the following constraints: + Unknowns may be negative. + Order: + f' i' j' constant G P n' + -1 )(if #[ 0 -1 1 5] +(list #[ 1 3 -3 -15] +#[ 1 1 -1 -5] +#[ 1 -1 1 5] +) +() +) +) +\end{verbatim} +which should be read as: +\begin{eqnarray*} + (f',i',j') & = & {\tt if}\; -P+n'-5 \geq 0 \\ + & & {\tt then} \; (G+3P-3n'-15, G+P-n'-5,G-P+n'+5) \\ + & & {\tt else} \; \bot +\end{eqnarray*} +That is, in the original coordinate system: +\[ (f,i,j) = {\tt if}\; n \geq 5 \; {\tt then} \; (-3n-15, -n-5, n+5) + \; {\tt else} \; \bot \] +I.e., the minimum value for function $f$ is $-3n-15$, and this value +is reached at point $(-n-5, n+5)$. This minimum exists only if $n \ge 5$; +otherwise, the feasible set is empty. + +\subsubsection{Mixed Programming} + +A mixed program is a program in which some variables are constrained +to be integers while others may take rational values. Suppose for +instance that we have to solve: +\begin{eqnarray*} +S & = & \min a x + b y,\\ + & & A x + B y + c \ge 0, +\end{eqnarray*} +where $y$ is the vector of the integer variables. First, solve + +\begin{eqnarray*} +T & = & \min a x,\\ + & & A x + B y + c \ge 0, +\end{eqnarray*} +in rational, with $y$ as parameters. The result is a quast. +To each leaf $i$ is associated a linear function $f_i(y)$ +and a set of inequalities $C_i y + d_i \ge 0$. $T$ is equal to +$f_i$ when $y$ is such that the corresponding inequalities +are satisfied. For each $i$, solve the problem: +\begin{eqnarray*} +S_i & = & \min f_i(y) + b y,\\ + & & C_i y + d_i \ge 0, +\end{eqnarray*} +in integers. The final result is the minimum of all $S_i$. +Obviously, the method can accomodate parameters in the +constraints. The $S_i$ will be functions of these +parameters, and the minimum must be computed symbolically. + +% +% an example is needed here +% +\section{Using the PIP Library} +The PIP Library (PipLib for short) was implemented to allow the user to call PIP +directly from his programs, without file accesses or system calls. The +user only needs to link his programs with C libraries. The +PipLib mainly provides one function which takes as input the problem description +and some options, and returns a {\tt Quast} (see grammar \ref{GrammarOutputData} +in section \ref{OutputData}) corresponding to the solution. Some +other functions are provided for convenience reasons ; they +are described in section \ref{PipLibfunc}. Most of them require +some specific structures to represent the problem or +the solution ; these structures are described in section \ref{PipLibdata}. + +\subsection{PipLib data structures description}\label{PipLibdata} +\subsubsection{PipMatrix structure} +\begin{verbatim} +struct pipmatrix +{ unsigned NbRows, NbColumns ; + Entier ** p ; + Entier * p_Init ; + int p_Init_size ; +} ; +typedef struct pipmatrix PipMatrix ; +\end{verbatim} +The {\tt PipMatrix} structure is devoted to represent a constraints matrix in the +PolyLib shape \cite{Wild:93}. The whole matrix is arranged row after row at the +{\tt p\_Init} adress. {\tt p} is an array of pointers in which +{\tt p[i]} points to the beginning of the i$^{th}$ row. +{\tt NbRows} and {\tt NbColumns} are respectively the number of +rows and columns of the matrix. We use this structure to carry polyhedrons. +Each row corresponds to a constraint which the polyhedron must satisfy. The +constraint is an equality if the first element is $0$, an inequality +$p(x) \geq 0$ if the first element is $1$. The next elements are +the unknown coefficients, followed by the parameter coefficients. +The last element is the constant factor. +For instance, in the problem of section \ref{exp2} the domain is defined by 3 +constraints: +\begin{displaymath} +\left\{ +\begin{array}{l} +-i + m \geq 0\\ +-j + n \geq 0\\ +j + i - k \geq 0 +\end{array} +\right. +\end{displaymath} +the rows corresponding to these constraints would be: +\begin{verbatim} +# eq/in i j k m n cst + 1 0 -1 0 1 0 0 + 1 -1 0 0 0 1 0 + 1 1 1 -1 0 0 0 +\end{verbatim} +The context is defined by one constraint: +\begin{displaymath} +\left\{ +\begin{array}{l} +-k + m + n \geq 0 +\end{array} +\right. +\end{displaymath} +the row corresponding to this constraint would be: +\begin{verbatim} +# eq/in k m n cst + 1 -1 1 1 0 +\end{verbatim} +{\tt p\_Init\_size} is needed by the polylib to free the memory allocated by +mpz\_init in the multiple precision release. + +\subsubsection{PipVector structure} +\begin{verbatim} +struct pipvector +{ int nb_elements ; + Entier * the_vector ; + Entier * the_deno ; +} ; +typedef struct pipvector PipVector ; +\end{verbatim} +The {\tt PipVector} structure represents a {\tt Vector} +as described in grammar \ref{GrammarOutputData} in section \ref{OutputData}. +{\tt nb\_elements} is the number of vector elements, {\tt the\_vector} is +an array which contains the numerators of these elements and {\tt the\_deno} +is an array which contains their denominators: the i$^{th}$ element is +{\tt the\_vector[i]/the\_deno[i]}. + +\subsubsection{PipNewparm structure} +\begin{verbatim} +struct pipnewparm +{ int rank ; + PipVector * vector ; + Entier deno ; + struct pipnewparm * next ; +} ; +typedef struct pipnewparm PipNewparm ; +\end{verbatim} +The {\tt PipNewparm} structure represents a {\tt NULL} terminated linked list of +{\tt Newparm} as described in grammar \ref{GrammarOutputData} +in section \ref{OutputData}. For each {\tt Newparm}, the rank is {\tt rank}, +the vector of coefficients is pointed by {\tt vector}, and the denominator +is {\tt deno}. {\tt next} is a pointer to the next {\tt PipNewparm} structure. + +\subsubsection{PipList structure} +\begin{verbatim} +struct piplist +{ PipVector * vector ; + struct piplist * next ; +} ; +typedef struct piplist PipList ; +\end{verbatim} +The {\tt PipList} structure represents a {\tt NULL} terminated linked list of +{\tt Vector} as described in grammar \ref{GrammarOutputData} in section +\ref{OutputData}. {\tt vector} is a pointer to the vector of the current node and +{\tt next} is a pointer to the next {\tt PipList} structure. + +\subsubsection{PipQuast structure} +\begin{verbatim} +struct pipquast +{ PipNewparm * newparm ; + PipList * list ; + PipVector * condition ; + struct pipquast * next_then ; + struct pipquast * next_else ; + struct pipquast * father ; +} ; +typedef struct pipquast PipQuast ; +\end{verbatim} +The {\tt PipQuast} represents a {\tt Quast} as described in +grammar \ref{GrammarOutputData} in section \ref{OutputData}. Each {\tt Quast} +has a tree structure and begins with a list of {\tt Newparm} +(field {\tt newparm}). If the pointer {\tt condition} is not {\tt NULL}, the +list of {\tt Newparm} is followed by a conditional structure : if the condition +pointed by {\tt condition} is true, then the solution continues in the +{\tt Quast} pointed by {\tt next\_then}, in the {\tt Quast} pointed by +{\tt next\_else} otherwise. If the pointer {\tt condition} is {\tt NULL}, the +list of {\tt Newparm} is followed by a list of vectors (field {\tt list}). +For {\tt Quast} manipulation convenience, a pointer to the father in the tree +is provided (field {\tt father}), obviously the father of the root is {\tt NULL}. + + +\subsubsection{PipOptions structure} +\begin{verbatim} +struct pipoptions +{ int Nq ; + int Verbose ; + int Simplify ; + int Deepest_cut ; + int Max ; +} ; +typedef struct pipoptions PipOptions ; +\end{verbatim} +The {\tt PipOptions} structure contains all the possible options ruling +the PIP behaviour and having to be set by the user: +\begin{enumerate} +\item {\tt Nq}: a boolean set to 1 if an integer solution is needed, 0 + otherwise, +\item {\tt Verbose}: a graduate value for debug informations: + \begin{itemize} + \item -1: absolute silence, + \item 0: relative silence, + \item 1: information on cuts when an integer solution is required, + \item 2: information on pivots and determinants, + \item 3: information on arrays. + \end{itemize} + Each option include the preceding one. + If {\tt Verbose} is not $-1$, most of the processing will be printed in + a file. The file name is generated at random (by \textit{mkstemp}) or + set with environment variable DEBUG. +\item {\tt Simplify}: a boolean set to 1 if some trivial quast simplifications + are needed (recursive elimination of degenerated patterns like + {\tt if \#[...] () ()}), 0 otherwise, +\item {\tt Deepest\_cut}: a boolean set to 1 if PIP has to use the deepest cut + algorithm, 0 otherwise, +\item {\tt Max}: a boolean set to 0 if the lexicographic + minimum is asked, or to 1 for the lexicographic maximum. When trying to + find the lexicographic maximum, the used method is the one + presented in section \ref{maximum}: if no bigparm was set, a new (big) + parameter is automatically created by adding a new ending column to the + constraint system (don't forget this when processing the output). +\end{enumerate} +Every {\tt PipOptions} structure should be created and filled with the default +values by the {\tt pip\_options\_init} function (see section \ref{optinit}). + +\subsection{PipLib functions description}\label{PipLibfunc} +\subsubsection{pip\_solve function} +\begin{verbatim} +PipQuast * pip_solve +( PipMatrix * domain, + PipMatrix * context, + int Bg, + PipOptions * options +) ; +\end{verbatim} +The {\tt pip\_solve} function solves a linear problem provided as input. The +first three parameters describe the problem that the user wants to solve. +The last parameter describe the options that the user has to set. +These parameters are: +\begin{enumerate} +\item {\tt domain}: a pointer to the equations and inequations system which + describes the unknown domain in the PolyLib constraints matrix shape, +\item {\tt context}: a pointer to the equations and inequations system satisfied + by the parameters context in the PolyLib constraints matrix shape + (it can be NULL if there is no context), +\item {\tt Bg}: the column rank of the bignum (first column rank is 0), or a + negative value if there is no big parameter in the problem to be solved, +\item {\tt options}: a pointer to a data structure containing the options + ruling the behaviour of PIP. +\end{enumerate} +This function returns a pointer to a {\tt PipQuast} structure containing the +solution, it will be {\tt NULL} if the context is {\tt void}. + +\subsubsection{pip\_options\_init function}\label{optinit} +\begin{verbatim} +PipOptions * pip_options_init(void) ; +\end{verbatim} +The {\tt pip\_options\_init} function allocates the memory space for a +{\tt PipOptions} structure and fills it with the default values: +\begin{itemize} +\item {\tt Nq} $= 1$: an integer value is required, +\item {\tt Verbose} $= 0$: no debug informations, +\item {\tt Simplify} $= 0$: do not try to simplify solutions, +\item {\tt Deepest\_cut} $= 0$: do not use deepest cut algorithm, +\item {\tt Max} $= 0$: compute the lexicographic minimum. +\end{itemize} +We strongly recommand to use this function to create and initialize any +{\tt PipOptions} structure. In this way, if some new options appear in +the future, there will be no compatibility problems. + +\subsubsection{pip\_close function} +\begin{verbatim} +void pip_close(void) ; +\end{verbatim} +The {\tt pip\_close} frees the memory space that have been allocated for +few global variables PipLib needs. This function has to be called when +PipLib is no more useful in order to prevent slight memory leaks. + +\subsubsection{pip\_matrix\_alloc function} +\begin{verbatim} +PipMatrix * pip_matrix_alloc +( unsigned nb_rows, + unsigned nb_columns +) ; +\end{verbatim} +The {\tt pip\_matrix\_alloc} function allocates the memory space +for a {\tt PipMatrix} structure with {\tt nb\_rows} rows and {\tt nb\_columns} +columns. It fills the {\tt Nb\_Rows}, {\tt Nb\_Columns} and {\tt p} fields +and initializes the matrix entries to 0, then it returns a pointer to this +structure. + +\subsubsection{pip\_matrix\_read function} +\begin{verbatim} +PipMatrix * pip_matrix_read(FILE *) ; +\end{verbatim} +The {\tt pip\_matrix\_read} function read a matrix from a file. It takes +as input a pointer to the file it has to read (possibly {\tt stdin}), and +returns a pointer to a {\tt PipMatrix} structure. The input has the following syntax: +\begin{itemize} +\item some optional comment lines which begin with {\tt \#}, +\item the row numbers and column numbers, possibly followed by comments, + on a single line, +\item the matrix rows, each row must be on a single line and is possibly + followed by comments. +\end{itemize} +For instance, in the problem of section \ref{exp2} the domain is defined as follows +\begin{verbatim} +# This is the domain +3 7 # 3 lines and 7 columns +1 0 -1 0 1 0 0 # -i + m >= 0 +1 -1 0 0 0 1 0 # -j + n >= 0 +1 1 1 -1 0 0 0 # j + i - k >= 0 +\end{verbatim} + +\subsubsection{Printing Functions} +\begin{verbatim} +void pip_matrix_print(FILE *, PipMatrix *) ; +void pip_vector_print(FILE *, PipVector *) ; +void pip_newparm_print(FILE *, PipNewparm *, int indent) ; +void pip_list_print(FILE *, PipList *, int indent) ; +void pip_quast_print(FILE *, PipQuast *, int indent) ; +void pip_options_print(FILE *, PipOptions *) ; +\end{verbatim} +There is a printing function for each structure of the PipLib. They all take as input +a pointer to a file (possibly {\tt stdout}) and a pointer to a structure. +Some of them takes as input an +indent step. They print the structure contents to the file without indent if +{\tt indent} $< 0$, with an indentation step of {\tt indent} otherwise. + +\subsubsection{Memory Deallocation Functions} +\begin{verbatim} +void pip_matrix_free(PipMatrix *) ; +void pip_vector_free(PipVector *) ; +void pip_newparm_free(PipNewparm *) ; +void pip_list_free(PipList *) ; +void pip_quast_free(PipQuast *) ; +void pip_options_free(PipOptions *) ; +\end{verbatim} +There is a memory deallocation function for each structure of the PipLib. +They free the allocated memory for the structure. + +\subsection{Example} +Here is a simple example showing how one can use the PipLib, assuming that +a basic installation was done. The following C program reads a domain and its +context on the standard input then prints the solution on the standard output. +Options are preselected : there is no bignum, we are looking for an integral +solution without simplification and we don't want debug informations. +\begin{verbatim} +/* example.c */ +# include +# include + +int main() +{ PipMatrix * domain, * context ; + PipQuast * solution ; + PipOptions * options ; + + domain = pip_matrix_read(stdin) ; + context = pip_matrix_read(stdin) ; + options = pip_options_init() ; + + solution = pip_solve(domain,context,-1,options) ; + + pip_options_free(options) ; + pip_matrix_free(domain) ; + pip_matrix_free(context) ; + + pip_quast_print(stdout,solution,0) ; + pip_close() ; +} +\end{verbatim} +The compilation command could be : +\begin{verbatim} +gcc example.c -lpiplib64 -o example +\end{verbatim} +Supposing that the user wants to solve the problem of section \ref{exp2}, he +will type: +\begin{verbatim} +3 7 +1 0 -1 0 1 0 0 +1 -1 0 0 0 1 0 +1 1 1 -1 0 0 0 +1 5 +1 -1 1 1 0 +\end{verbatim} +And the program will print : +\begin{verbatim} +(if #[ -1 1 0 0] + (list + #[ 0 0 0 0] + #[ 1 0 0 0] + ) + (list + #[ 1 -1 0 0] + #[ 0 1 0 0] + ) +) +\end{verbatim} + +\section{Installing PIP} + +\subsection{Implementation Notes} + +The main problem with any integer programming software is that, since one +must distinguish between integer and rationals, all computations are +to be done exactly. Rationals must be represented as quotients with +an integer numerator and an integer denominator. In the preceding version, +there was only one denominator for the whole tableau. The consequence +was that simplifications where most unlikely, and that the integers +in the tableau were growing until overflows occured. + +In the present version, there is one denominator per row of the tableau. +Reduction to lower terms occurs frequently, and the growth of numbers in the +problem tableau is limited. As a consequence, much larger problems can be +solved. This has had the unfortunate consequence that several bugs, which +were beyond the domain of the old version, have now surfaced. These bugs +have been corrected. As far as the author + can tell, these bugs mainly gave correct +results which were not in simplest form: the quast had extraneous leaves. +In some cases, the result was wrong but the error was self evident: for +instance, there were denominators in integer results. + +\subsection{License} +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License version 2 +as published by the Free Software Foundation. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. +{\tt http://www.gnu.org/copyleft/gpl.html} + +\subsection{Adjusting the Precision} +Pip is an all integer version of the dual simplex algorithm. As such, +it has to handle integers whose size may grow exponentially as the +computation proceeds. Integer overflow may occur and have to be checked. +Since the hardware integer overflow exception is usually masked by +the operating system or the compiler, overflow is detected by checking +that a division somewhere in the algorithm, which can be proved to be +exact by mathematical arguments, is indeed exact. If not, an error is +reported and the computation stops. + +The size of the numbers to be handled depends strongly on the size of the +constraint matrix and on the size of its coefficients. + +\subsubsection{Bounded Pip} +The precision of the integer representation in the Pip code can be +adjusted at compile time by giving options to the {\tt configure} +shell script. +By giving {\tt configure} the option {\tt --enable-llint} you ask +for long long int version only (64 bits). It results in a 64 bits Pip +called {\tt pip64}. +By giving {\tt configure} the option {\tt --enable-int} you +ask for int version only. It results in a 32 bits called +{\tt pip32} and a faster running time. + +\subsubsection{Multiple Precision Pip} +Multiple Precision Pip is built on top of the GMP library +(this library is freely available at {\tt http://www.swox.com/gmp}). +Each integer in the program is represented as a list of 32 bits numbers. +All computations are done exactly, and the size of the numbers increases +as needed to preserve exactness. It follows that no overflow is possible. +However, when the size of numbers increases, computations get slower and +slower, and memory overflow may occur in extreme cases. In well behaved +problems, 32 bits are enough for the initial data, the size of intermediate +results first increases up to a maximum, then decreses, and 32 bits +are again enough for the results. Hence, it has been possible to keep +the input format and output format of Multiple Precision Pip completely +compatible with the formats of the bounded precision versions. + +To install Multiple Precision Pip, first install Gmp according to the +directions found at the above URL. Usually, the library is installed +in {\tt /usr/local/lib}, and the header files are in {\tt /usr/local/include}. +If this is not the case, you must adjust the Pip makefile by giving +to the {\tt configure} shell script the option {\tt --with-gmp=PATH}, where +{\tt PATH} is the GMP library installation path. + +By giving {\tt configure} the option {\tt --enable-gmp} you ask +for a GMP version only. It results in a multiple precision Pip +called {\tt pipMP}. + + +\subsection{Building the Executable and the Library} + +To build PIP, first copy the above tarfile to any convenient directory. +Expand the tarfile using: +\begin{verbatim} +zcat pip.tar.Z | tar xvf - +\end{verbatim} +You should obtain the following files: +\begin{itemize} +\item header files in the {\tt include} directory, +\item C code files in the {\tt source} directory, +\item a lot of data files {\tt *.dat} and of result files {\tt *.ll} + in the {\tt test} directory (you should then run at least some of + the {\tt *.dat} files and compare the results to the corresponding + {\tt *.ll} file), +\item a simple example showing how to use the PipLib in the {\tt example} directory, +\item a postscript version of the present document, {\tt pip.ps} in the + {\tt doc} directory, +\item files needed for compilation and installation in the PIP + root directory. +\end{itemize} + + +\subsubsection{basic installation} + +The {\tt configure} shell script attempts to guess correct values for +various system-dependent variables used during compilation. It uses +those values to create a {\tt Makefile}. +The file {\tt configure.in} is used to create {\tt configure} by a program +called {\tt autoconf}. You only need {\tt configure.in} if you want to change +it or regenerate {\tt configure} using a newer version of {\tt autoconf}. + +The simplest way to compile this package is: +\begin{itemize} +\item {\tt cd} to the directory containing the package's source code and type \linebreak + {\tt ./configure} to configure the package for your system + (while running, {\tt configure} prints some + messages telling which features it is checking for), + +\item type {\tt make} to compile the package and install the program and the + library, + +\item you can remove the program binaries and object files from the + source code directory by typing {\tt make clean}. To also remove the + files that {\tt configure} created (so you can compile the package for + a different kind of computer) type {\tt make distclean}. +\end{itemize} + +PIP and the PipLib have been successfully compiled on the following systems: +\begin{itemize} +\item PC's under Linux, with the {\tt gcc} compiler, +\item PC's under Windows (Cygwin), with the {\tt gcc} compiler (but because +of some Cygwin limitations, only 32 bits version will work and user may +experience some problems when linking with PipLib), +\item SparcStations, with the {\tt gcc} compiler. +\end{itemize} + +\subsubsection{optionnal features} + +\begin{itemize} +\item By default, {\tt make} will install the package's files in +{\tt /usr/local/bin}, \linebreak {\tt /usr/local/lib}, etc. You can specify an +installation prefix other than {\tt /usr/local} by giving {\tt configure} the +option {\tt --prefix=PATH}. + +\item By default, both PIP and the PipLib are compiled and installed. By giving +{\tt configure} the option {\tt --without-pip} you disable the compilation and +installation of PIP. By giving {\tt configure} the option {\tt --without-lib} +you disable the compilation and installation of the PipLib. + +\item By default, both int (32 bits) and long long int (64 bits) versions are +built. Multiple precision is built too if the GMP library is found. +By giving {\tt configure} the option {\tt --enable-int} you ask for int +version only. By giving {\tt configure} the option {\tt --enable-llint} you +ask for long long int version only. By giving {\tt configure} the +option {\tt --enable-gmp} you ask for GMP version only. + +\item By default, PIP looks for the GMP library in the standard path +({\tt /usr/} or {\tt /usr/local/}). If the multiple precision Pip construction +is needed and if the GMP library was installed elsewhere, you must must give +to the {\tt configure} shell script the option {\tt --with-gmp=PATH}, where +{\tt PATH} is the GMP library installation path. Another possibility is to +give the GMP include and/or library path separately by using +{\tt --with-gmp-include=PATH} and {\tt --with-gmp-library=PATH}. +\end{itemize} + +\subsubsection{uninstallation} +You can easily remove PIP and the PipLib from your system by typing +{\tt make uninstall}. + +\vspace{0.5cm} +Report all bugs, problems, inaccuracies in the documentation to: + +{\tt Paul.Feautrier@ens-lyon.fr} + +{\tt Cedric.Bastoul@prism.uvsq.fr} + +Praise is also appreciated. + +Let the power of parametric integer programming be with you. + +\bibliography{% +/users/prism/pf/local/biblio/totale% +,/users/prism/pf/local/biblio/second% +,/users/prism/pf/local/biblio/quater% +} + +\end{document} diff --git a/example/Makefile b/example/Makefile index dec4bb2..5cb3d59 100644 --- a/example/Makefile +++ b/example/Makefile @@ -1,7 +1,7 @@ # Please enter here the locations for PipLib include and libraries if they # aren't the default values (/usr/lib and /usr/include). -PIPLIB_INC = /usr/local/include #$(HOME)/progs/linux/include -PIPLIB_LIB = /usr/local/lib #$(HOME)/progs/linux/lib +PIPLIB_INC = $(HOME)/progs/linux/include +PIPLIB_LIB = $(HOME)/progs/linux/lib CC = gcc LDLIBS= -lpiplib32 diff --git a/example/sor1d.pip b/example/sor1d.pip new file mode 100644 index 0000000..1bef89e --- /dev/null +++ b/example/sor1d.pip @@ -0,0 +1,28 @@ +2 4 + 1 1 0 0 + 1 0 1 0 + +-1 + +20 8 + + 0 -1 0 0 0 0 0 2 + 0 0 -1 0 0 0 0 1 + 0 0 0 -1 0 0 0 2 + 0 0 0 0 -1 0 0 4 + 1 0 0 0 1 0 0 -2 + 1 -2 0 2 1 0 0 -4 + 1 0 0 0 -1 0 1 -1 + 1 2 0 -2 -1 0 0 5 + 1 0 0 1 0 0 0 -1 + 1 0 -2 1 0 0 0 0 + 1 -2 0 2 0 0 1 -5 + 1 0 0 -1 0 1 0 0 + 1 0 2 -1 0 0 0 1 + 1 2 0 -2 0 0 0 3 + 1 0 1 0 0 0 0 0 + 1 -2 4 0 0 0 1 -3 + 1 0 -2 0 0 1 0 0 + 1 2 -4 0 0 0 0 3 + 1 2 0 0 0 0 0 1 + 1 -2 0 0 0 2 1 -5 diff --git a/include/piplib/funcall.h b/include/piplib/funcall.h index 1079f34..6c6a168 100644 --- a/include/piplib/funcall.h +++ b/include/piplib/funcall.h @@ -4,7 +4,7 @@ * funcall.h * ****************************************************************************** * * - * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002 * + * Copyright Paul Feautrier, 1988-2005 * * * * This is free software; you can redistribute it and/or modify it under the * * terms of the GNU General Public License as published by the Free Software * @@ -49,7 +49,9 @@ void sol_reset(int); struct high_water_mark tab_hwm(void); Tableau *tab_get(FILE *, int,int,int); void sol_init(void); +void sol_close(void); void tab_init(void); +void tab_close(void); void sol_if(void); void sol_forme(int); void sol_val(Entier, Entier); diff --git a/include/piplib/piplib.h b/include/piplib/piplib.h index e7b082c..3c149a0 100644 --- a/include/piplib/piplib.h +++ b/include/piplib/piplib.h @@ -4,7 +4,7 @@ * piplib.h * ****************************************************************************** * * - * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002 * + * Copyright Paul Feautrier, 1988-2005 * * * * This is free software; you can redistribute it and/or modify it under the * * terms of the GNU General Public License as published by the Free Software * @@ -46,6 +46,7 @@ # include # define Entier mpz_t # define FORMAT "%d" +# define GMP_INPUT_FORMAT "%lZd" #endif #ifndef PIPLIB_H @@ -191,6 +192,11 @@ void pip_options_free(PipOptions *) ; PipMatrix * pip_matrix_alloc(unsigned, unsigned) ; PipMatrix * pip_matrix_read(FILE *) ; PipOptions * pip_options_init(void) ; + + +/* initialization of pip library */ +void pip_init(); +void pip_close(); /* Prototype de la fonction de resolution : diff --git a/include/piplib/type.h b/include/piplib/type.h index 4030537..8a2fb60 100644 --- a/include/piplib/type.h +++ b/include/piplib/type.h @@ -31,6 +31,11 @@ extern "C" { #endif +/* Modified by Serge Torres to handle very big problems (since 1.3.4 we can put + * any value we want: sol_space is allocated dynamically), but it is left by + * default to 4096 because of time/space reasons for most people. + * #define SOL_SIZE 67108864 + */ #define SOL_SIZE 4096 extern Entier UN; diff --git a/source/maind.c b/source/maind.c index 7fa8b48..7b93ee1 100644 --- a/source/maind.c +++ b/source/maind.c @@ -4,7 +4,7 @@ * maind.h * ****************************************************************************** * * - * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002 * + * Copyright Paul Feautrier, 1988-2005 * * * * This is free software; you can redistribute it and/or modify it under the * * terms of the GNU General Public License as published by the Free Software * @@ -91,10 +91,11 @@ int main(int argc, char *argv[]) int p, q, xq; long temps; char *date; + Entier x ; #if defined(LINEAR_VALUE_IS_MP) - int x ; + mpz_init(x); #else - Entier x, i; + Entier i; #endif #if defined(LINEAR_VALUE_IS_MP) @@ -129,14 +130,14 @@ int main(int argc, char *argv[]) { fprintf(stderr, "%s unaccessible\n", g); verbose = 0; } - } + } else { mkstemp(dump_name); dump = fopen(dump_name, "w"); } } - if(strcmp(argv[p], "-d") == 0) - { deepest_cut = 1; + if(argc>p && strcmp(argv[p], "-d") == 0) + { deepest_cut = 1; p++; } } @@ -172,6 +173,26 @@ int main(int argc, char *argv[]) {if(c != '(') continue; fprintf(out, "("); balance(in, out); + #if defined(LINEAR_VALUE_IS_MP) + if(dscanf(in, x) < 0){escape(in, out, 1); continue;} + else + nvar = mpz_get_si(x); + if(dscanf(in, x) < 0){escape(in, out, 1); continue;} + else + nparm = mpz_get_si(x); + if(dscanf(in, x) < 0){escape(in, out, 1); continue;} + else + ni = mpz_get_si(x); + if(dscanf(in, x) < 0){escape(in, out, 1); continue;} + else + nc = mpz_get_si(x); + if(dscanf(in, x) < 0){escape(in, out, 1); continue;} + else + bigparm = mpz_get_si(x); + if(dscanf(in, x) < 0){escape(in, out, 1); continue;} + else + nq = mpz_get_si(x); + #else if(dscanf(in, &x) < 0){escape(in, out, 1); continue;} else nvar = (int) x; @@ -190,6 +211,8 @@ int main(int argc, char *argv[]) if(dscanf(in, &x) < 0){escape(in, out, 1); continue;} else nq = (int) x; + #endif + if(verbose > 0) {fprintf(dump, "%d %d %d %d %d %d\n",nvar, nparm, ni, nc, bigparm, nq); fflush(dump); @@ -246,6 +269,11 @@ int main(int argc, char *argv[]) fprintf(stderr, "n %d u %d''' s %d'''\r\n", comptage, chrono.tms_utime, chrono.tms_stime); #endif + +#if defined(LINEAR_VALUE_IS_MP) + mpz_clear(x); +#endif + pip_close(); exit(0); } diff --git a/source/piplib.c b/source/piplib.c index c3112f6..7ea3c89 100644 --- a/source/piplib.c +++ b/source/piplib.c @@ -4,7 +4,7 @@ * piplib.c * ****************************************************************************** * * - * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002 * + * Copyright Paul Feautrier, 1988-2005 * * * * This is free software; you can redistribute it and/or modify it under the * * terms of the GNU General Public License as published by the Free Software * @@ -77,7 +77,7 @@ int dgetc(FILE *foo) #if defined(LINEAR_VALUE_IS_MP) -int dscanf(FILE *foo, int *val) +int dscanf(FILE *foo, Entier val) #else int dscanf(FILE *foo, Entier *val) #endif @@ -101,7 +101,11 @@ int dscanf(FILE *foo, Entier *val) && inbuff[inptr] != '\n' && inbuff[inptr] != '\t') break; } + #if defined(LINEAR_VALUE_IS_MP) + if(gmp_sscanf(inbuff+inptr, GMP_INPUT_FORMAT, val) != 1) + #else if(sscanf(inbuff+inptr, FORMAT, val) != 1) + #endif return -1; for(; inptr < proviso; inptr++) @@ -581,6 +585,37 @@ PipMatrix * pip_matrix_read(FILE * foo) } return matrix ; } + + +/* initialization of pip */ +static int pip_initialized = 0; + +void pip_init() { + /* Avoid initializing (and leaking) several times */ + if (!pip_initialized) { + #if defined(LINEAR_VALUE_IS_MP) + mpz_init_set_si(UN, 1); + mpz_init_set_si(ZERO, 0); + #else + UN = VAL_UN ; + ZERO = VAL_ZERO ; + #endif + sol_init() ; + tab_init() ; + pip_initialized = 1; + } +} + +void pip_close() { + tab_close(); + sol_close(); +# if defined(LINEAR_VALUE_IS_MP) + mpz_clear(UN); + mpz_clear(ZERO); +# endif + pip_initialized = 0; +} + /****************************************************************************** @@ -622,21 +657,8 @@ PipOptions * options ; struct high_water_mark hq ; Entier D ; PipQuast * solution ; - static int pip_initialized = 0; - - /* Avoid initializing (and leaking) several times */ - if (!pip_initialized) { - #if defined(LINEAR_VALUE_IS_MP) - mpz_init_set_si(UN, 1); - mpz_init_set_si(ZERO, 0); - #else - UN = VAL_UN ; - ZERO = VAL_ZERO ; - #endif - sol_init() ; - tab_init() ; - pip_initialized = 1; - } + + pip_init() ; /* initialisations diverses : * - la valeur de Verbose et Deepest_cut sont placees dans leurs variables diff --git a/source/sol.c b/source/sol.c index f695b48..0edc745 100644 --- a/source/sol.c +++ b/source/sol.c @@ -49,7 +49,7 @@ struct S #define Val 7 #define Error 8 -struct S sol_space[SOL_SIZE]; +struct S * sol_space; static int sol_free; #if !defined(LINEAR_VALUE_IS_MP) @@ -69,6 +69,12 @@ Entier pgcd(Entier x, Entier y) void sol_init(void) { sol_free = 0; + sol_space = (struct S *)malloc(SOL_SIZE*sizeof(struct S)) ; +} + +void sol_close(void) +{ + free(sol_space) ; } int sol_hwm() diff --git a/source/tab.c b/source/tab.c index c3e406f..0e1ef42 100644 --- a/source/tab.c +++ b/source/tab.c @@ -41,7 +41,7 @@ static int chunk_count; int dgetc(FILE *); #if defined(LINEAR_VALUE_IS_MP) -int dscanf(FILE *, int *); +int dscanf(FILE *, Entier); #else int dscanf(FILE *, Entier *); #endif @@ -64,6 +64,13 @@ void tab_init(void) tab_base->free = tab_free; chunk_count = 1; } + + +void tab_close(void) +{ + if (tab_base) free(tab_base); +} + struct high_water_mark tab_hwm(void) {struct high_water_mark p; @@ -219,10 +226,9 @@ int h, w, n; { Tableau *p; int i, j, c; - #if defined(LINEAR_VALUE_IS_MP) - int x ; - #else Entier x; + #if defined(LINEAR_VALUE_IS_MP) + mpz_init(x); #endif p = tab_alloc(h, w, n); @@ -237,17 +243,24 @@ int h, w, n; #endif while((c = dgetc(foo)) != EOF)if(c == '[')break; for(j = 0; jrow[i].objet.val[j], x); + if(dscanf(foo, x) < 0) + return NULL; + else + mpz_set(p->row[i].objet.val[j], x); #else - p->row[i].objet.val[j] = x; + if(dscanf(foo, &x) < 0) + return NULL; + else + p->row[i].objet.val[j] = x; #endif } } while((c = dgetc(foo)) != EOF)if(c == ']')break; + + #if defined(LINEAR_VALUE_IS_MP) + mpz_clear(x); + #endif return(p); } diff --git a/source/traiter.c b/source/traiter.c index 4300414..eaf9807 100644 --- a/source/traiter.c +++ b/source/traiter.c @@ -4,7 +4,7 @@ * traiter.c * ****************************************************************************** * * - * Copyright Paul Feautrier, 1988, 1993, 1994, 1996, 2002 * + * Copyright Paul Feautrier, 1988-2005 * * * * This is free software; you can redistribute it and/or modify it under the * * terms of the GNU General Public License as published by the Free Software * @@ -575,8 +575,8 @@ int pivoter(Tableau *tp, int pivi, int nvar, int nparm, int ni, int iq) p = tp->row[k].objet.val; for(j = 0; jrow[pivi].objet.val; diff --git a/test/makefile b/test/makefile index cb1e24a..5696fc5 100644 --- a/test/makefile +++ b/test/makefile @@ -86,7 +86,7 @@ test: if [ $$failedtest != 0 ]; then \ echo "$$failedtest tests failed"; \ else \ - echo "PIP works correctly :0)"; \ + echo "PIP works correctly :-)"; \ fi # Include the shared compilation rules -- 2.11.4.GIT