105 | | }//proc delete_dublicates_noteval |
106 | | |
107 | | //================================================== |
| 497 | }//proc delete_duplicates_noteval |
| 498 | |
| 499 | |
| 500 | static proc test_delete_duplicates_noteval() |
| 501 | {//testing delete_duplicates_noteval |
| 502 | int result = 1; |
| 503 | //Test 1: empty list should return empty list |
| 504 | list expected= list(); |
| 505 | list obtained = delete_duplicates_noteval(list()); |
| 506 | if (!isListEqual(expected, obtained)) |
| 507 | { |
| 508 | print("Test 1 failed for delete_duplicates_noteval."); |
| 509 | print("Expected:\n"); |
| 510 | print(expected); |
| 511 | print("obtained:\n"); |
| 512 | print(obtained); |
| 513 | result = 0; |
| 514 | } |
| 515 | //Test 2: one element list |
| 516 | expected = list(list(1,15)); |
| 517 | obtained = delete_duplicates_noteval(list(list(1,15))); |
| 518 | if (!isListEqual(expected,obtained)) |
| 519 | { |
| 520 | print("Test 2 failed for delete_duplicates_noteval."); |
| 521 | print("Expected:\n"); |
| 522 | print(expected); |
| 523 | print("obtained:\n"); |
| 524 | print(obtained); |
| 525 | result = 0; |
| 526 | } |
| 527 | //Test 3: Two empty lists in input list |
| 528 | expected = list(list()); |
| 529 | obtained = delete_duplicates_noteval(list(list(),list())); |
| 530 | if (!isListEqual(expected,obtained)) |
| 531 | { |
| 532 | print("Test 3 failed for delete_duplicates_noteval."); |
| 533 | print("Expected:\n"); |
| 534 | print(expected); |
| 535 | print("obtained:\n"); |
| 536 | print(obtained); |
| 537 | result = 0; |
| 538 | } |
| 539 | ring r = 0,(x,y),dp; |
| 540 | setring r; |
| 541 | //Test 4: Typical output for factorization algorithm, no repeat |
| 542 | expected = list(list(1,x,y),list(1,y,x)); |
| 543 | obtained = delete_duplicates_noteval(expected); |
| 544 | if (!isListEqual(obtained,expected)) |
| 545 | { |
| 546 | print("Test 4 failed for delete_duplicates_noteval"); |
| 547 | result = 0; |
| 548 | } |
| 549 | //Test 5: Typical output for factorization algorithm, repeat |
| 550 | expected =list(list(1,x,y),list(1,y,x)); |
| 551 | list input = insert(expected, list(1,x,y)); |
| 552 | obtained = delete_duplicates_noteval(input); |
| 553 | if (!isListEqual(expected,obtained)) |
| 554 | { |
| 555 | print("Test 5 failed for delete_duplicates_noteval"); |
| 556 | result = 0; |
| 557 | } |
| 558 | return(result); |
| 559 | }//testing delete_duplicates_noteval |
| 560 | |
| 561 | |
| 562 | static proc delete_duplicates_noteval_and_sort(list l) |
| 563 | " |
| 564 | INPUT: A list of lists; Output same as e.g. FacFirstWeyl. Containing different factorizations |
| 565 | of a polynomial |
| 566 | OUTPUT: If there are duplicates in this list, this procedure deletes them and returns the list |
| 567 | without double entries. Furthermore, it sorts the list |
| 568 | " |
| 569 | {//proc delete_duplicates_noteval_and_sort |
| 570 | list result= sortFactorizations(l); |
| 571 | int i; |
| 572 | for (i=1; i<size(result);i++) |
| 573 | { |
| 574 | if (isFactorizationEqual(result[i],result[i+1])) |
| 575 | { |
| 576 | result = delete(result, i); |
| 577 | continue; |
| 578 | } |
| 579 | } |
| 580 | return(result); |
| 581 | }//proc delete_duplicates_noteval_and_sort |
| 582 | |
| 583 | |
| 584 | static proc test_delete_duplicates_noteval_and_sort() |
| 585 | {//testing delete_duplicates_noteval_and_sort |
| 586 | int result = 1; |
| 587 | //Test 1: empty list should return empty list |
| 588 | list expected = list(); |
| 589 | list obtained = delete_duplicates_noteval_and_sort(list()); |
| 590 | if (!isListEqual(obtained,expected)) |
| 591 | { |
| 592 | print("Test 1 failed for delete_duplicates_noteval_and_sort."); |
| 593 | print("Expected:\n"); |
| 594 | print(expected); |
| 595 | print("obtained:\n"); |
| 596 | print(obtained); |
| 597 | result = 0; |
| 598 | } |
| 599 | //Test 2: one element list |
| 600 | expected = list(list(1,15)); |
| 601 | obtained = delete_duplicates_noteval_and_sort(list(list(1,15))); |
| 602 | if (!isListEqual(expected,obtained)) |
| 603 | { |
| 604 | print("Test 2 failed for delete_duplicates_noteval_and_sort."); |
| 605 | print("Expected:\n"); |
| 606 | print(expected); |
| 607 | print("obtained:\n"); |
| 608 | print(obtained); |
| 609 | result = 0; |
| 610 | } |
| 611 | //Test 3: Two empty lists in input list |
| 612 | expected = list(list()); |
| 613 | obtained = delete_duplicates_noteval_and_sort(list(list(),list())); |
| 614 | if (!isListEqual(expected,obtained)) |
| 615 | { |
| 616 | print("Test 3 failed for delete_duplicates_noteval_and_sort."); |
| 617 | print("Expected:\n"); |
| 618 | print(expected); |
| 619 | print("obtained:\n"); |
| 620 | print(obtained); |
| 621 | result = 0; |
| 622 | } |
| 623 | ring r = 0,(x,y),dp; |
| 624 | setring r; |
| 625 | //Test 4: Typical output for factorization algorithm, no repeat |
| 626 | list input = list(list(1,x,y),list(1,y,x)); |
| 627 | expected = input; |
| 628 | obtained = delete_duplicates_noteval_and_sort(input); |
| 629 | if (!isListEqual(obtained,expected)) |
| 630 | { |
| 631 | print("Test 4 failed for delete_duplicates_noteval_and_sort"); |
| 632 | print("Expected:\n"); |
| 633 | print(expected); |
| 634 | print("obtained:\n"); |
| 635 | print(obtained); |
| 636 | result = 0; |
| 637 | } |
| 638 | //Test 5: Typical output for factorization algorithm, repeat |
| 639 | input=insert(input, list(1,x,y)); |
| 640 | expected = list(list(1,x,y),list(1,y,x)); |
| 641 | obtained = delete_duplicates_noteval_and_sort(input); |
| 642 | if (!isListEqual(expected,obtained)) |
| 643 | { |
| 644 | print("Test 5 failed for delete_duplicates_noteval_and_sort"); |
| 645 | print("Expected:\n"); |
| 646 | print(expected); |
| 647 | print("obtained:\n"); |
| 648 | print(obtained); |
| 649 | result = 0; |
| 650 | } |
| 651 | //Test 6: Typical output for factorization algorithm, no repeat, unsorted |
| 652 | input = list(list(1,y,x),list(1,x,y)); |
| 653 | expected = list(list(1,x,y),list(1,y,x)); |
| 654 | obtained = delete_duplicates_noteval_and_sort(input); |
| 655 | if (!isListEqual(expected,obtained)) |
| 656 | { |
| 657 | print("Test 6 failed for delete_duplicates_noteval_and_sort"); |
| 658 | print("Expected:\n"); |
| 659 | print(expected); |
| 660 | print("obtained:\n"); |
| 661 | print(obtained); |
| 662 | result = 0; |
| 663 | } |
| 664 | //Test 7: Typical output for factorization algorithm, repeat, |
| 665 | //unsorted |
| 666 | input=insert(input, list(1,x,y)); |
| 667 | expected = list(list(1,x,y),list(1,y,x)); |
| 668 | obtained = delete_duplicates_noteval_and_sort(input); |
| 669 | if (!isListEqual(expected,obtained)) |
| 670 | { |
| 671 | print("Test 7 failed for delete_duplicates_noteval_and_sort"); |
| 672 | result = 0; |
| 673 | } |
| 674 | return(result); |
| 675 | }//delete_duplicates_noteval_and_sort |
| 676 | |
| 677 | |
| 678 | static proc combinekfinlf(list g, int nof) |
| 679 | " |
| 680 | given a list of factors g and a desired size nof, this |
| 681 | procedure combines the factors, such that we receive a |
| 682 | list of the length nof. |
| 683 | INPUT: A list of containing polynomials or any type where the *-operator is existent |
| 684 | OUTPUT: All possibilities (without permutation of the given list) to combine the polynomials |
| 685 | into nof polynomials given by the user. |
| 686 | " |
| 687 | {//Procedure combinekfinlf |
| 688 | list result; |
| 689 | int i; int j; int k; //iteration variables |
| 690 | list fc; //fc stands for "factors combined" |
| 691 | list temp; //a temporary store for factors |
| 692 | def nofgl = size(g); //nofgl stands for "number of factors of the given list" |
| 693 | if (nofgl == 0) |
| 694 | {//g was the empty list |
| 695 | return(result); |
| 696 | }//g was the empty list |
| 697 | if (nof <= 0) |
| 698 | {//The user wants to recieve a negative number or no element as a result |
| 699 | return(result); |
| 700 | }//The user wants to recieve a negative number or no element as a result |
| 701 | if (nofgl == nof) |
| 702 | {//There are no factors to combine |
| 703 | result = result + list(g); |
| 704 | return(result); |
| 705 | }//There are no factors to combine |
| 706 | if (nof == 1) |
| 707 | {//User wants to get just one factor |
| 708 | result = result + list(list(product(g))); |
| 709 | return(result); |
| 710 | }//User wants to get just one factor |
| 711 | if(nof>nofgl) |
| 712 | {//something is so wrong. Just returning the original list |
| 713 | result = result + list(g); |
| 714 | return(result); |
| 715 | }//something is so wrong. Just returning the original list |
| 716 | def leftPart; |
| 717 | list rightPart; |
| 718 | list recResult; |
| 719 | for (i = 1; i<=nofgl-nof+1; i++) |
| 720 | {//combine first i and recursive call results |
| 721 | recResult = list(); |
| 722 | rightPart = list(); |
| 723 | leftPart = g[1]; |
| 724 | for (j=2; j<=i; j++) |
| 725 | {//filling the leftPart |
| 726 | leftPart = leftPart * g[j]; |
| 727 | }//filling the leftPart |
| 728 | for (j=i+1; j<=nofgl; j++) |
| 729 | { rightPart[j-i] = g[j]; } |
| 730 | recResult = combinekfinlf(rightPart, nof-1); |
| 731 | for (j=1; j<=size(recResult); j++) |
| 732 | {//pushing the left part in |
| 733 | recResult[j] = insert(recResult[j],leftPart,0); |
| 734 | }//pushing the left part in |
| 735 | result = result + recResult; |
| 736 | }//combine first i and recursive call results |
| 737 | result = delete_duplicates_noteval_and_sort(result); |
| 738 | return(result); |
| 739 | }//Procedure combinekfinlf |
| 740 | |
| 741 | |
| 742 | static proc test_combinekfinlf() |
| 743 | {//testing combinekfinlf |
| 744 | int result = 1; |
| 745 | //Test1: The usual same old empty list |
| 746 | list expected = list(); |
| 747 | list obtained = combinekfinlf(list(),5); |
| 748 | if (!isListEqual(obtained,expected)) |
| 749 | { |
| 750 | print("Test 1 for combinekfinlf failed.\n"); |
| 751 | print("Expected:\n"); |
| 752 | print(expected); |
| 753 | print("obtained:\n"); |
| 754 | print(obtained); |
| 755 | result = 0; |
| 756 | } |
| 757 | //Test2: list of length 1, nof=0 |
| 758 | expected = list(); |
| 759 | obtained = combinekfinlf(list(1),0); |
| 760 | if (!isListEqual(expected,obtained)) |
| 761 | { |
| 762 | print("Test 2 for combinekfinlf failed."); |
| 763 | print("Expected:\n"); |
| 764 | print(expected); |
| 765 | print("obtained:\n"); |
| 766 | print(obtained); |
| 767 | result = 0; |
| 768 | } |
| 769 | //Test3: list of length 1, nof=1 |
| 770 | expected= list(list(5)); |
| 771 | obtained = combinekfinlf(list(5),1); |
| 772 | if (!isListEqual(expected, obtained)) |
| 773 | { |
| 774 | print("Test 3 for combinekfinlf failed."); |
| 775 | print("Expected:\n"); |
| 776 | print(expected); |
| 777 | print("obtained:\n"); |
| 778 | print(obtained); |
| 779 | result = 0; |
| 780 | } |
| 781 | //Test4: list of length 1, nof > 1 |
| 782 | expected = (list(list(5))); |
| 783 | obtained = combinekfinlf(list(5),5); |
| 784 | if (!isListEqual(expected, obtained)) |
| 785 | { |
| 786 | print("Test 4 for combinekfinlf failed."); |
| 787 | print("Expected:\n"); |
| 788 | print(expected); |
| 789 | print("obtained:\n"); |
| 790 | print(obtained); |
| 791 | result = 0; |
| 792 | } |
| 793 | //Test5: list of larger length, nof = 1 |
| 794 | expected=list(list(1*2*3*4*5*6)); |
| 795 | obtained= combinekfinlf(list(1,2,3,4,5,6),1); |
| 796 | if (!isListEqual(expected, obtained)) |
| 797 | { |
| 798 | print("Test 5 for combinekfinlf failed."); |
| 799 | print("Expected:\n"); |
| 800 | print(expected); |
| 801 | print("obtained:\n"); |
| 802 | print(obtained); |
| 803 | result = 0; |
| 804 | } |
| 805 | //Test6: list of larger length, nof = 2 |
| 806 | expected= delete_duplicates_noteval_and_sort( |
| 807 | list(list(1,2*3*4*5*6),list(2,3*4*5*6), |
| 808 | list(1*2*3,4*5*6),list(1*2*3*4,5*6), |
| 809 | list(1*2*3*4*5,6))); |
| 810 | obtained = combinekfinlf(list(1,2,3,4,5,6),2); |
| 811 | if (!isListEqual(expected, obtained)) |
| 812 | { |
| 813 | print("Test 6 for combinekfinlf failed."); |
| 814 | print("Expected:\n"); |
| 815 | print(expected); |
| 816 | print("obtained:\n"); |
| 817 | print(obtained); |
| 818 | result = 0; |
| 819 | } |
| 820 | //Test7: list of larger length, nof = length of list |
| 821 | expected = list(list(1,2,3,4,5,6)); |
| 822 | obtained = combinekfinlf(list(1,2,3,4,5,6),6); |
| 823 | if (!isListEqual(expected, obtained)) |
| 824 | { |
| 825 | print("Test 7 for combinekfinlf failed."); |
| 826 | print("Expected:\n"); |
| 827 | print(expected); |
| 828 | print("obtained:\n"); |
| 829 | print(obtained); |
| 830 | result = 0; |
| 831 | } |
| 832 | //Test8 list of larger length, nof = half of the length |
| 833 | expected = delete_duplicates_noteval_and_sort( |
| 834 | list(list(1,2,3*4*5*6),list(1,2*3,4*5*6), |
| 835 | list(1,2*3*4,5*6),list(1,2*3*4*5,6), |
| 836 | list(1*2,3,4*5*6),list(1*2,3*4,5*6), |
| 837 | list(1*2,3*4*5,6),list(1*2*3,4,5*6), |
| 838 | list(1*2*3,4*5,6),list(1*2*3*4,5,6))); |
| 839 | obtained = (combinekfinlf(list(1,2,3,4,5,6),3)); |
| 840 | if (!isListEqual(expected, obtained)) |
| 841 | { |
| 842 | print("Test 8 for combinekfinlf failed."); |
| 843 | print("Expected:\n"); |
| 844 | print(expected); |
| 845 | print("obtained:\n"); |
| 846 | print(obtained); |
| 847 | result = 0; |
| 848 | } |
| 849 | return(result); |
| 850 | }//testing combinekfinlf |
| 851 | |
| 852 | |
| 853 | static proc permpp(list l) |
| 854 | " |
| 855 | INPUT: A list with entries of a type, where the ==-operator is defined |
| 856 | OUTPUT: A list with all permutations of this given list. |
| 857 | " |
| 858 | {//proc permpp |
| 859 | int i; int j; |
| 860 | list tempresult; |
| 861 | list l_without_double; |
| 862 | list l_without_double_pos; |
| 863 | int double_entry; |
| 864 | list result; |
| 865 | if (size(l)==0) |
| 866 | { |
| 867 | return(list()); |
| 868 | } |
| 869 | if (size(l)==1) |
| 870 | { |
| 871 | return(list(l)); |
| 872 | } |
| 873 | for (i = 1; i<=size(l);i++) |
| 874 | {//Filling the list with unique entries |
| 875 | double_entry = 0; |
| 876 | for (j = 1; j<=size(l_without_double);j++) |
| 877 | { |
| 878 | if (l_without_double[j] == l[i]) |
| 879 | { |
| 880 | double_entry = 1; |
| 881 | break; |
| 882 | } |
| 883 | } |
| 884 | if (!double_entry) |
| 885 | { |
| 886 | l_without_double = l_without_double + list(l[i]); |
| 887 | l_without_double_pos = l_without_double_pos + list(i); |
| 888 | } |
| 889 | }//Filling the list with unique entries |
| 890 | for (i = 1; i<=size(l_without_double); i++ ) |
| 891 | { |
| 892 | tempresult = permpp(delete(l,l_without_double_pos[i])); |
| 893 | for (j = 1; j<=size(tempresult);j++) |
| 894 | { |
| 895 | tempresult[j] = list(l_without_double[i])+tempresult[j]; |
| 896 | } |
| 897 | result = result+tempresult; |
| 898 | } |
| 899 | return(result); |
| 900 | }//proc permpp |
| 901 | |
| 902 | |
| 903 | static proc test_permpp() |
| 904 | {//testing permpp |
| 905 | int result = 1; |
| 906 | //Test 1: empty list |
| 907 | list expected = list(); |
| 908 | list obtained = permpp(list()); |
| 909 | if (!isListEqual(expected, obtained)) |
| 910 | { |
| 911 | print("Test 1 for permpp failed."); |
| 912 | print("Expected:\n"); |
| 913 | print(expected); |
| 914 | print("obtained:\n"); |
| 915 | print(obtained); |
| 916 | result = 0; |
| 917 | } |
| 918 | //Test 2: 1 element list |
| 919 | expected = list(list(1)); |
| 920 | obtained = permpp(list(1)); |
| 921 | if (!isListEqual(expected, obtained)) |
| 922 | { |
| 923 | print("Test 2 for permpp failed."); |
| 924 | print("Expected:\n"); |
| 925 | print(expected); |
| 926 | print("obtained:\n"); |
| 927 | print(obtained); |
| 928 | result = 0; |
| 929 | } |
| 930 | //Test 3: multi-element list, but only one unique element. |
| 931 | expected = list(list(2,2,2,2,2,2,2)); |
| 932 | obtained = permpp(list(2,2,2,2,2,2,2)); |
| 933 | if (!isListEqual(expected, obtained)) |
| 934 | { |
| 935 | print("Test 3 for permpp failed."); |
| 936 | print("Expected:\n"); |
| 937 | print(expected); |
| 938 | print("obtained:\n"); |
| 939 | print(obtained); |
| 940 | result = 0; |
| 941 | } |
| 942 | //Test 4: multi-element list, all elements distinct |
| 943 | expected = sortFactorizations( |
| 944 | list(list(1,2,3,4),list(1,2,4,3),list(1,3,2,4), |
| 945 | list(1,3,4,2),list(1,4,2,3),list(1,4,3,2), |
| 946 | list(2,1,3,4),list(2,1,4,3),list(2,4,1,3), |
| 947 | list(2,4,3,1),list(2,3,1,4),list(2,3,4,1), |
| 948 | list(3,1,2,4),list(3,1,4,2),list(3,2,1,4), |
| 949 | list(3,2,4,1),list(3,4,1,2),list(3,4,2,1), |
| 950 | list(4,1,2,3),list(4,1,3,2),list(4,2,1,3), |
| 951 | list(4,2,3,1),list(4,3,1,2),list(4,3,2,1))); |
| 952 | obtained = sortFactorizations(permpp(list(1,2,3,4))); |
| 953 | if (!isListEqual(expected, obtained)) |
| 954 | { |
| 955 | print("Test 4 for permpp failed."); |
| 956 | print("Expected:\n"); |
| 957 | print(expected); |
| 958 | print("obtained:\n"); |
| 959 | print(obtained); |
| 960 | result = 0; |
| 961 | } |
| 962 | //Test5: multi-element list, same elements available. |
| 963 | expected = sortFactorizations( |
| 964 | list(list(1,2,2,3),list(1,2,3,2),list(1,3,2,2), |
| 965 | list(2,1,2,3),list(2,1,3,2),list(2,2,1,3), |
| 966 | list(2,2,3,1),list(2,3,1,2),list(2,3,2,1), |
| 967 | list(3,2,2,1),list(3,2,1,2),list(3,1,2,2))); |
| 968 | obtained = sortFactorizations(permpp(list(1,2,2,3))); |
| 969 | if (!isListEqual(expected, obtained)) |
| 970 | { |
| 971 | print("Test 5 for permpp failed."); |
| 972 | print("Expected:\n"); |
| 973 | print(expected); |
| 974 | print("obtained:\n"); |
| 975 | print(obtained); |
| 976 | result = 0; |
| 977 | } |
| 978 | return(result); |
| 979 | }//testing permpp |
| 980 | |
| 981 | |
| 982 | static proc binarySearch(def inputList, def inputElem) |
| 983 | " |
| 984 | INPUT: An iterable inputList (ideal/vector/intvec), which has to be |
| 985 | sorted, and an element inputElem, for which it has to be |
| 986 | possible to compare it to the other elements. |
| 987 | OUTPUT: If the entry was found, it returns its position, otherwise it returns 0. |
| 988 | " |
| 989 | {//binarySearch |
| 990 | int first = 1; |
| 991 | int last = size(inputList); |
| 992 | int middle; |
| 993 | while (first <= last) |
| 994 | { |
| 995 | middle = first + ((last - first) div 2); |
| 996 | if (inputList[middle] < inputElem) |
| 997 | { |
| 998 | first = middle + 1; |
| 999 | } |
| 1000 | else |
| 1001 | { |
| 1002 | if (inputList[middle] > inputElem) |
| 1003 | { |
| 1004 | last = middle -1; |
| 1005 | } |
| 1006 | else |
| 1007 | { |
| 1008 | return(middle); |
| 1009 | } |
| 1010 | } |
| 1011 | } |
| 1012 | return(0); |
| 1013 | }//binarySearch |
| 1014 | |
| 1015 | |
| 1016 | static proc test_binarySearch() |
| 1017 | {//testing binarySearch |
| 1018 | int result = 1; |
| 1019 | //Test 1: Empty list |
| 1020 | int expected = 0; |
| 1021 | int obtained = binarySearch(list(),5); |
| 1022 | if (expected != obtained) |
| 1023 | { |
| 1024 | print("Test 1 for binarySearch failed."); |
| 1025 | print("Expected:\n"); |
| 1026 | print(expected); |
| 1027 | print("obtained:\n"); |
| 1028 | print(obtained); |
| 1029 | result = 0; |
| 1030 | } |
| 1031 | //Test2: One element list, element not found |
| 1032 | expected = 0; |
| 1033 | obtained = binarySearch(list(1),2); |
| 1034 | if (expected != obtained) |
| 1035 | { |
| 1036 | print("Test 2 for binarySearch failed."); |
| 1037 | print("Expected:\n"); |
| 1038 | print(expected); |
| 1039 | print("obtained:\n"); |
| 1040 | print(obtained); |
| 1041 | result = 0; |
| 1042 | } |
| 1043 | //Test3: One element list, element found |
| 1044 | expected = 1; |
| 1045 | obtained = binarySearch(list(1),1); |
| 1046 | if (expected != obtained) |
| 1047 | { |
| 1048 | print("Test 3 for binarySearch failed."); |
| 1049 | print("Expected:\n"); |
| 1050 | print(expected); |
| 1051 | print("obtained:\n"); |
| 1052 | print(obtained); |
| 1053 | result = 0; |
| 1054 | } |
| 1055 | //Test4: Two element list, element not found |
| 1056 | expected = 0; |
| 1057 | obtained = binarySearch(list(1,3),2); |
| 1058 | if (expected != obtained) |
| 1059 | { |
| 1060 | print("Test 4 for binarySearch failed."); |
| 1061 | print("Expected:\n"); |
| 1062 | print(expected); |
| 1063 | print("obtained:\n"); |
| 1064 | print(obtained); |
| 1065 | result = 0; |
| 1066 | } |
| 1067 | //Test5: Two element list, element found |
| 1068 | expected = 2; |
| 1069 | obtained = binarySearch(list(1,2),2); |
| 1070 | if (expected != obtained) |
| 1071 | { |
| 1072 | print("Test 5 for binarySearch failed."); |
| 1073 | print("Expected:\n"); |
| 1074 | print(expected); |
| 1075 | print("obtained:\n"); |
| 1076 | print(obtained); |
| 1077 | result = 0; |
| 1078 | } |
| 1079 | //Test6: Multi element list, element not found |
| 1080 | expected =0; |
| 1081 | obtained = binarySearch(list(1,2,6,9,15,22),5); |
| 1082 | if (expected != obtained) |
| 1083 | { |
| 1084 | print("Test 6 for binarySearch failed."); |
| 1085 | print("Expected:\n"); |
| 1086 | print(expected); |
| 1087 | print("obtained:\n"); |
| 1088 | print(obtained); |
| 1089 | result = 0; |
| 1090 | } |
| 1091 | //Test7: Multi element list, element found |
| 1092 | expected =4; |
| 1093 | obtained = binarySearch(list(1,2,6,9,15,22),9); |
| 1094 | if (expected != obtained) |
| 1095 | { |
| 1096 | print("Test 7 for binarySearch failed."); |
| 1097 | print("Expected:\n"); |
| 1098 | print(expected); |
| 1099 | print("obtained:\n"); |
| 1100 | print(obtained); |
| 1101 | result = 0; |
| 1102 | } |
| 1103 | return(result); |
| 1104 | }//testing binarySearch |
| 1105 | |
| 1106 | |
| 1107 | static proc getAllDivisorsFromFactList(list l) |
| 1108 | "USAGE: getAllDivisorsFromFactList(l); l is a list containing two |
| 1109 | lists; first list represents the prime factors, second list |
| 1110 | their powers. |
| 1111 | RETURNS: list(int) |
| 1112 | PURPOSE: Computes all possible factors of the integer n, whose |
| 1113 | factorization into prime factors is defined by l; |
| 1114 | ASSUMPTIONS: |
| 1115 | - The list is containing two lists. They can be assumed to be outputs of the function |
| 1116 | factorizeInt. They have at least one entry. If it is exactly one entry, the second intvec should |
| 1117 | contain a value at least 2. |
| 1118 | " |
| 1119 | {//proc getAllDivisorsFromFactList |
| 1120 | list primeFactors=l[1]; |
| 1121 | list powersOfThem = l[2]; |
| 1122 | int i;int j; |
| 1123 | //Casting the entries to be numbers |
| 1124 | for (i=1; i<=size(primeFactors); i++) |
| 1125 | { |
| 1126 | primeFactors[i] = number(primeFactors[i]); |
| 1127 | powersOfThem[i] = number(powersOfThem[i]); |
| 1128 | } |
| 1129 | |
| 1130 | //Alternative Code |
| 1131 | list result; |
| 1132 | number tempPrimeFactor = 1; |
| 1133 | list recursiveCall; |
| 1134 | list recursivePowersOfThem; |
| 1135 | if (size(primeFactors)==1) |
| 1136 | {//base case: we can right away compute the result and return it. |
| 1137 | for (i = 1; i<=powersOfThem[1];i++) |
| 1138 | { |
| 1139 | tempPrimeFactor = tempPrimeFactor*primeFactors[1]; |
| 1140 | result = insert(result,tempPrimeFactor); |
| 1141 | } |
| 1142 | }//base case: we can right away compute the result and return it. |
| 1143 | else |
| 1144 | {//non-base-case that involves recursion. |
| 1145 | if (powersOfThem[1] == 1) |
| 1146 | {//we have used up all our powers of that prime |
| 1147 | recursiveCall = |
| 1148 | getAllDivisorsFromFactList(list(delete(primeFactors,1),delete(powersOfThem,1))); |
| 1149 | }//we have used up all our powers of that prime |
| 1150 | else |
| 1151 | {//There is more power to that one prime |
| 1152 | recursivePowersOfThem = powersOfThem; |
| 1153 | recursivePowersOfThem[1] = recursivePowersOfThem[1] -1; |
| 1154 | recursiveCall = getAllDivisorsFromFactList(list(primeFactors, recursivePowersOfThem)); |
| 1155 | }//There is more power to that one prime |
| 1156 | result = recursiveCall; |
| 1157 | for (i=1; i<=size(recursiveCall); i++) |
| 1158 | {//inserting the possibilities with the one factor included. |
| 1159 | result = insert(result, recursiveCall[i]*primeFactors[1]); |
| 1160 | }//inserting the possibilities with the one factor included. |
| 1161 | }//non-base-case that involves recursion. |
| 1162 | result = insert(result,number(1)); |
| 1163 | result = sort(result)[1]; |
| 1164 | result = delete_duplicates_noteval(result); |
| 1165 | return(result); |
| 1166 | }//proc getAllDivisorsFromFactList |
| 1167 | |
| 1168 | |
| 1169 | static proc test_getAllDivisorsFromFactList() |
| 1170 | {//testing getAllDivisorsFromFactList |
| 1171 | int result = 1; |
| 1172 | ring R = 0,(x),dp; |
| 1173 | //Test 1: factor of 1 |
| 1174 | list expected = list(number(1)); |
| 1175 | list obtained = getAllDivisorsFromFactList(factorizeInt(1)); |
| 1176 | if (!isListEqual(expected, obtained)) |
| 1177 | { |
| 1178 | print("Test 1 for getAllDivisorsFromFactList failed."); |
| 1179 | print("Expected:\n"); |
| 1180 | print(expected); |
| 1181 | print("obtained:\n"); |
| 1182 | print(obtained); |
| 1183 | result = 0; |
| 1184 | } |
| 1185 | //Test2: single prime |
| 1186 | expected = list(number(1),number(5)); |
| 1187 | obtained = getAllDivisorsFromFactList(factorizeInt(5)); |
| 1188 | if (!isListEqual(expected, obtained)) |
| 1189 | { |
| 1190 | print("Test 2 for getAllDivisorsFromFactList failed."); |
| 1191 | print("Expected:\n"); |
| 1192 | print(expected); |
| 1193 | print("obtained:\n"); |
| 1194 | print(obtained); |
| 1195 | result = 0; |
| 1196 | } |
| 1197 | //Test3: prime power |
| 1198 | expected = list(number(1),number(2),number(4),number(8)); |
| 1199 | obtained = getAllDivisorsFromFactList(factorizeInt(8)); |
| 1200 | if (!isListEqual(expected, obtained)) |
| 1201 | { |
| 1202 | print("Test 3 for getAllDivisorsFromFactList failed."); |
| 1203 | print("Expected:\n"); |
| 1204 | print(expected); |
| 1205 | print("obtained:\n"); |
| 1206 | print(obtained); |
| 1207 | result = 0; |
| 1208 | } |
| 1209 | //Test4: Arbitrary number |
| 1210 | expected = list(number(1),number(2),number(5),number(10)); |
| 1211 | obtained = getAllDivisorsFromFactList(factorizeInt(10)); |
| 1212 | if (!isListEqual(expected, obtained)) |
| 1213 | { |
| 1214 | print("Test 2 for getAllDivisorsFromFactList failed."); |
| 1215 | print("Expected:\n"); |
| 1216 | print(expected); |
| 1217 | print("obtained:\n"); |
| 1218 | print(obtained); |
| 1219 | result = 0; |
| 1220 | } |
| 1221 | return(result); |
| 1222 | }//testing getAllDivisorsFromFactList |
| 1223 | |
| 1224 | |
| 1225 | static proc triangNum(int n) |
| 1226 | "Returns the nth triangular number." |
| 1227 | { |
| 1228 | if (n == 0) |
| 1229 | { |
| 1230 | return(0); |
| 1231 | } |
| 1232 | return (n*(n+1) div 2); |
| 1233 | } |
| 1234 | |
| 1235 | |
| 1236 | static proc test_triangNum() |
| 1237 | {//testing triangNum |
| 1238 | int result = 1; |
| 1239 | //Test 1: 0 |
| 1240 | int expected = 0; |
| 1241 | int obtained = triangNum(0); |
| 1242 | if (expected !=obtained) |
| 1243 | { |
| 1244 | print("Test 1 for tringNum failed."); |
| 1245 | print("Expected:\n"); |
| 1246 | print(expected); |
| 1247 | print("obtained:\n"); |
| 1248 | print(obtained); |
| 1249 | result = 0; |
| 1250 | } |
| 1251 | //Test 2: 1 |
| 1252 | expected = 1; |
| 1253 | obtained = triangNum(1); |
| 1254 | if (expected !=obtained) |
| 1255 | { |
| 1256 | print("Test 2 for tringNum failed."); |
| 1257 | print("Expected:\n"); |
| 1258 | print(expected); |
| 1259 | print("obtained:\n"); |
| 1260 | print(obtained); |
| 1261 | result = 0; |
| 1262 | } |
| 1263 | //Test 3: some non-trivial higher number (gauss) |
| 1264 | expected = 5050; |
| 1265 | obtained = triangNum(100); |
| 1266 | if (expected !=obtained) |
| 1267 | { |
| 1268 | print("Test 3 for tringNum failed."); |
| 1269 | print("Expected:\n"); |
| 1270 | print(expected); |
| 1271 | print("obtained:\n"); |
| 1272 | print(obtained); |
| 1273 | result = 0; |
| 1274 | } |
| 1275 | return(result); |
| 1276 | }//testing triangNum |
| 1277 | |
| 1278 | |
| 1279 | |
| 1280 | static proc fromListToIntvec(list l) |
| 1281 | "Converter from List to intvec. |
| 1282 | Assuming all entries in the given |
| 1283 | list are integers, and the list is not empty." |
| 1284 | { |
| 1285 | intvec result; int i; |
| 1286 | for (i = 1; i<=size(l); i++) |
| 1287 | { |
| 1288 | result[i] = l[i]; |
| 1289 | } |
| 1290 | return(result); |
| 1291 | } |
| 1292 | |
| 1293 | |
| 1294 | static proc test_fromListToIntvec() |
| 1295 | {//testing fromListToIntvec |
| 1296 | int result = 1; |
| 1297 | //Test 1: List with 1 element |
| 1298 | list input = list(1); |
| 1299 | intvec expected = intvec(1); |
| 1300 | intvec obtained = fromListToIntvec(input); |
| 1301 | if (expected !=obtained) |
| 1302 | { |
| 1303 | print("Test 1 for fromListToIntvec failed."); |
| 1304 | print("Expected:\n"); |
| 1305 | print(expected); |
| 1306 | print("obtained:\n"); |
| 1307 | print(obtained); |
| 1308 | result = 0; |
| 1309 | } |
| 1310 | //Test 2: List with more than 1 element |
| 1311 | input = list(1,6,3,2); |
| 1312 | expected = intvec(1,6,3,2); |
| 1313 | obtained = fromListToIntvec(input); |
| 1314 | if (expected !=obtained) |
| 1315 | { |
| 1316 | print("Test 2 for fromListToIntvec failed."); |
| 1317 | print("Expected:\n"); |
| 1318 | print(expected); |
| 1319 | print("obtained:\n"); |
| 1320 | print(obtained); |
| 1321 | result = 0; |
| 1322 | } |
| 1323 | return(result); |
| 1324 | }//testing fromListToIntvec |
| 1325 | |
| 1326 | |
| 1327 | static proc fromIntvecToList(intvec l)" |
| 1328 | Converter from intvec to list" |
| 1329 | {//proc fromIntvecToList |
| 1330 | list result = list(); |
| 1331 | int i; |
| 1332 | for (i = size(l); i>=1; i--) |
| 1333 | { |
| 1334 | result = insert(result, l[i]); |
| 1335 | } |
| 1336 | return(result); |
| 1337 | }//proc fromIntvecToList |
| 1338 | |
| 1339 | static proc test_fromIntvecToList() |
| 1340 | {//testing fromIntvecToList |
| 1341 | int result = 1; |
| 1342 | //Test1: Intvec(0) |
| 1343 | intvec input; |
| 1344 | list expected = list(0); |
| 1345 | list obtained = fromIntvecToList(input); |
| 1346 | if (!isListEqual(expected,obtained)) |
| 1347 | { |
| 1348 | print("Test 1 for fromIntvecToList failed."); |
| 1349 | print("Expected:\n"); |
| 1350 | print(expected); |
| 1351 | print("obtained:\n"); |
| 1352 | print(obtained); |
| 1353 | result = 0; |
| 1354 | } |
| 1355 | //Test2: Intvec(1) |
| 1356 | input= intvec(1); |
| 1357 | expected = list(1); |
| 1358 | obtained = fromIntvecToList(input); |
| 1359 | if (!isListEqual(expected,obtained)) |
| 1360 | { |
| 1361 | print("Test 2 for fromIntvecToList failed."); |
| 1362 | print("Expected:\n"); |
| 1363 | print(expected); |
| 1364 | print("obtained:\n"); |
| 1365 | print(obtained); |
| 1366 | result = 0; |
| 1367 | } |
| 1368 | //Test 3: Intvec with arbitarily many elements |
| 1369 | input= intvec(6,4,7,1,24); |
| 1370 | expected = list(6,4,7,1,24); |
| 1371 | obtained = fromIntvecToList(input); |
| 1372 | if (!isListEqual(expected,obtained)) |
| 1373 | { |
| 1374 | print("Test 3 for fromIntvecToList failed."); |
| 1375 | print("Expected:\n"); |
| 1376 | print(expected); |
| 1377 | print("obtained:\n"); |
| 1378 | print(obtained); |
| 1379 | result = 0; |
| 1380 | } |
| 1381 | return(result); |
| 1382 | }//testing fromIntvecToList |
| 1383 | |
| 1384 | |
| 1385 | static proc produceHomogListForProduct(list homogParts1, list homogParts2) |
| 1386 | " |
| 1387 | INPUT: Two lists of integer vectors, homogParts1 and homogParts2, |
| 1388 | where the contained integer vectors all have the same size n. |
| 1389 | OUTPUT: One list of integer vectors, which have size n respectively. |
| 1390 | The entries form a subset of possible integer vectors which result |
| 1391 | of a sum of an entry y in homogParts1 and an entry x in |
| 1392 | homogParts2. |
| 1393 | The subset is given by the property that for each index i in |
| 1394 | homogparts1, the i'th entry in the resulting list has |
| 1395 | homogparts1[i] as a summand. Furthermore, |
| 1396 | result[length(result)-i] should also have |
| 1397 | homogparts1[length(homogparts)-i] as a summand. |
| 1398 | " |
| 1399 | {//produceHomogListForProduct |
| 1400 | int i; int j; int k; |
| 1401 | list p = reverse(sort(homogParts1)[1]); |
| 1402 | list q = reverse(sort(homogParts2)[1]); |
| 1403 | list result; |
| 1404 | intvec tempIntVec; |
| 1405 | for (i = 1; i<= size(homogParts1); i++) |
| 1406 | { |
| 1407 | for (j = 1; j<= size(homogParts2); j++) |
| 1408 | { |
| 1409 | tempIntVec = homogParts1[i] + homogParts2[j]; |
| 1410 | if (binarySearch(result,tempIntVec)==0) |
| 1411 | {//Element was not yet in result, add it |
| 1412 | result = result + list(tempIntVec); |
| 1413 | result = sort(result)[1]; |
| 1414 | }//Element was not yet in result, add it |
| 1415 | } |
| 1416 | } |
| 1417 | if (size(result)==0) |
| 1418 | { |
| 1419 | return(result); |
| 1420 | } |
| 1421 | result = reverse(result); |
| 1422 | //Till here, we have a complete list with entries that are between hmax and hmin |
| 1423 | //Now, we need to filter this list. |
| 1424 | |
| 1425 | int isIn; |
| 1426 | for(i = 1; i<=size(p); i++) |
| 1427 | {//Checking, if homogparts[i] has a counterpart in homogparts2 |
| 1428 | isIn = 0; |
| 1429 | for (j = 1; j<=size(q); j++) |
| 1430 | {//iterating through the counterparts |
| 1431 | if(p[i] + q[j] == result[i]) |
| 1432 | { |
| 1433 | isIn = 1; |
| 1434 | break; |
| 1435 | } |
| 1436 | }//iterating through the counterparts |
| 1437 | if(!isIn) |
| 1438 | { |
| 1439 | result = delete(result,i); |
| 1440 | continue; |
| 1441 | } |
| 1442 | }//Checking, if homogparts[i] has a counterpart in homogparts2 |
| 1443 | for (i = 0; i<size(p); i++) |
| 1444 | {//The same from the top |
| 1445 | isIn = 0; |
| 1446 | for (j = 1; j<=size(q); j++) |
| 1447 | {//iterating through the counterparts |
| 1448 | if(p[size(p)-i] + q[j] == result[size(result) - i]) |
| 1449 | { |
| 1450 | isIn = 1; |
| 1451 | break; |
| 1452 | } |
| 1453 | }//iterating through the counterparts |
| 1454 | if(!isIn) |
| 1455 | { |
| 1456 | result = delete(result,size(result)-i); |
| 1457 | continue; |
| 1458 | } |
| 1459 | }//The same from the top |
| 1460 | return(result); |
| 1461 | }//produceHomogListForProduct |
| 1462 | |
| 1463 | |
| 1464 | static proc test_produceHomogListForProduct() |
| 1465 | {//testing produceHomogListForProduct |
| 1466 | int result = 1; |
| 1467 | //Test 1: Both lists are empty |
| 1468 | list expected = list(); |
| 1469 | list obtained = produceHomogListForProduct(list(),list()); |
| 1470 | if (!isListEqual(expected, obtained)) |
| 1471 | { |
| 1472 | print("Test 1 for produceHomogListForProduct failed."); |
| 1473 | print("Expected:\n"); |
| 1474 | print(expected); |
| 1475 | print("obtained:\n"); |
| 1476 | print(obtained); |
| 1477 | result = 0; |
| 1478 | } |
| 1479 | //Test 2: one list empty, the other one contains elements. |
| 1480 | expected = list(); |
| 1481 | list input1 = list(); |
| 1482 | list input2 = list(intvec(1,2,3),intvec(4,5,6)); |
| 1483 | obtained = produceHomogListForProduct(input1,input2); |
| 1484 | if (!isListEqual(expected, obtained)) |
| 1485 | { |
| 1486 | print("Test 2 for produceHomogListForProduct failed."); |
| 1487 | print("Expected:\n"); |
| 1488 | print(expected); |
| 1489 | print("obtained:\n"); |
| 1490 | print(obtained); |
| 1491 | result = 0; |
| 1492 | } |
| 1493 | //Test 3: one list contains elements, the other list is empty. |
| 1494 | expected = list(); |
| 1495 | input2 = list(); |
| 1496 | input1 = list(intvec(1,2,3),intvec(4,5,6)); |
| 1497 | obtained = produceHomogListForProduct(input1,input2); |
| 1498 | if (!isListEqual(expected, obtained)) |
| 1499 | { |
| 1500 | print("Test 3 for produceHomogListForProduct failed."); |
| 1501 | print("Expected:\n"); |
| 1502 | print(expected); |
| 1503 | print("obtained:\n"); |
| 1504 | print(obtained); |
| 1505 | result = 0; |
| 1506 | } |
| 1507 | //Test 4: each list has one element |
| 1508 | expected = list(intvec(5,7,9)); |
| 1509 | input1 = list(intvec(4,5,6)); |
| 1510 | input2 = list(intvec(1,2,3)); |
| 1511 | obtained = produceHomogListForProduct(input1,input2); |
| 1512 | if (!isListEqual(expected, obtained)) |
| 1513 | { |
| 1514 | print("Test 4 for produceHomogListForProduct failed."); |
| 1515 | print("Expected:\n"); |
| 1516 | print(expected); |
| 1517 | print("obtained:\n"); |
| 1518 | print(obtained); |
| 1519 | result = 0; |
| 1520 | } |
| 1521 | //Test5: Random multiple elements, different size |
| 1522 | expected = list(intvec(19,23,2),intvec(5,7,9),intvec(4,4,4)); |
| 1523 | input1 = list(intvec(4,5,6),intvec(3,2,1),intvec(11,15,1)); |
| 1524 | input2 = list(intvec(1,2,3),intvec(8,8,1)); |
| 1525 | obtained = produceHomogListForProduct(input1,input2); |
| 1526 | if (!isListEqual(expected, obtained)) |
| 1527 | { |
| 1528 | print("Test 5 for produceHomogListForProduct failed."); |
| 1529 | print("Expected:\n"); |
| 1530 | print(expected); |
| 1531 | print("obtained:\n"); |
| 1532 | print(obtained); |
| 1533 | result = 0; |
| 1534 | } |
| 1535 | //Test6: Random multiple elements, same size |
| 1536 | expected = list(intvec(19,23,2),intvec(5,7,9)); |
| 1537 | input1 = list(intvec(4,5,6),intvec(11,15,1)); |
| 1538 | input2 = list(intvec(1,2,3),intvec(8,8,1)); |
| 1539 | obtained = produceHomogListForProduct(input1,input2); |
| 1540 | if (!isListEqual(expected, obtained)) |
| 1541 | { |
| 1542 | print("Test 6 for produceHomogListForProduct failed."); |
| 1543 | print("Expected:\n"); |
| 1544 | print(expected); |
| 1545 | print("obtained:\n"); |
| 1546 | print(obtained); |
| 1547 | result = 0; |
| 1548 | } |
| 1549 | return(result); |
| 1550 | }//testing produceHomogListForProduct |
| 1551 | |
| 1552 | |
| 1553 | static proc possibleHomogPartsInBetween(intvec pmax, intvec pmin, intvec maxDegrees) |
| 1554 | " |
| 1555 | INPUT: Integer vectors pmax, pmin and maxDegrees. All are of the same size, |
| 1556 | except from maxDegrees, which is double of the size of the rest. |
| 1557 | OUTPUT: A list of possible points in Z^n that can lie between pmax and |
| 1558 | pmin, sorted with respect to the lexicographic order from |
| 1559 | biggest to smallest (leftmost entry in the intvec is the biggest), |
| 1560 | represented as list of intvecs. Upper bounds are given by maxDegrees. |
| 1561 | " |
| 1562 | {//possibleHomogPartsInBetween |
| 1563 | if (size(pmax) != size(pmin) || 2*size(pmax)!=size(maxDegrees) || pmax<=pmin) |
| 1564 | { |
| 1565 | ERROR("pmax and pmin shall have the same size, and maxDegrees |
| 1566 | shall be double the size of both. Furhtermore, it must hold that pmax>pmin. The |
| 1567 | Input was: " + string(pmax) + ", " + string(pmin) + ", " + string(maxDegrees)); |
| 1568 | } |
| 1569 | list result; |
| 1570 | intvec tempIntVec = pmax; |
| 1571 | while(tempIntVec > pmin) |
| 1572 | { |
| 1573 | result = result + list(tempIntVec); |
| 1574 | tempIntVec = nextSmallerEntry(tempIntVec,pmin,maxDegrees); |
| 1575 | } |
| 1576 | result = result + list(pmin); |
| 1577 | return (sort(result)[1]); |
| 1578 | }//possibleHomogPartsInBetween |
| 1579 | |
| 1580 | |
| 1581 | static proc test_possibleHomogPartsInBetween() |
| 1582 | {//testing possibleHomogPartsInBetween |
| 1583 | int result = 1; |
| 1584 | //Test 1: Nothing in between |
| 1585 | list expected = list(intvec(1,1),intvec(1,2)); |
| 1586 | list obtained = |
| 1587 | possibleHomogPartsInBetween(intvec(1,2), |
| 1588 | intvec(1,1), |
| 1589 | intvec(10,10,10,10)); |
| 1590 | if (!isListEqual(expected, obtained)) |
| 1591 | { |
| 1592 | print("Test 1 for possibleHomogPartsInBetween failed."); |
| 1593 | print("Expected:\n"); |
| 1594 | print(expected); |
| 1595 | print("obtained:\n"); |
| 1596 | print(obtained); |
| 1597 | result = 0; |
| 1598 | } |
| 1599 | //Test 2: exactly one intvec in between |
| 1600 | expected = list(intvec(1,1),intvec(1,2),intvec(1,3)); |
| 1601 | obtained = |
| 1602 | possibleHomogPartsInBetween(intvec(1,3), |
| 1603 | intvec(1,1), |
| 1604 | intvec(10,10,10,10)); |
| 1605 | if (!isListEqual(expected, obtained)) |
| 1606 | { |
| 1607 | print("Test 2 for possibleHomogPartsInBetween failed."); |
| 1608 | print("Expected:\n"); |
| 1609 | print(expected); |
| 1610 | print("obtained:\n"); |
| 1611 | print(obtained); |
| 1612 | result = 0; |
| 1613 | } |
| 1614 | //Test 3: One complete degree of freedom |
| 1615 | expected = list(intvec(1,1,1), |
| 1616 | intvec(1,1,2), |
| 1617 | intvec(1,1,3), |
| 1618 | intvec(1,1,4), |
| 1619 | intvec(1,1,5), |
| 1620 | intvec(1,2,-5), |
| 1621 | intvec(1,2,-4), |
| 1622 | intvec(1,2,-3), |
| 1623 | intvec(1,2,-2), |
| 1624 | intvec(1,2,-1), |
| 1625 | intvec(1,2,0), |
| 1626 | intvec(1,2,1), |
| 1627 | intvec(1,2,2), |
| 1628 | intvec(1,2,3), |
| 1629 | intvec(1,2,4), |
| 1630 | intvec(1,2,5), |
| 1631 | intvec(1,3,-5), |
| 1632 | intvec(1,3,-4), |
| 1633 | intvec(1,3,-3), |
| 1634 | intvec(1,3,-2), |
| 1635 | intvec(1,3,-1), |
| 1636 | intvec(1,3,0), |
| 1637 | intvec(1,3,1), |
| 1638 | intvec(1,3,2), |
| 1639 | intvec(1,3,3), |
| 1640 | intvec(1,3,4), |
| 1641 | intvec(1,3,5)); |
| 1642 | obtained = |
| 1643 | possibleHomogPartsInBetween(intvec(1,3,5), |
| 1644 | intvec(1,1,1), |
| 1645 | intvec(5,5,5,5,5,5)); |
| 1646 | if (!isListEqual(expected, obtained)) |
| 1647 | { |
| 1648 | print("Test 3 for possibleHomogPartsInBetween failed."); |
| 1649 | print("Expected:\n"); |
| 1650 | print(expected); |
| 1651 | print("obtained:\n"); |
| 1652 | print(obtained); |
| 1653 | result = 0; |
| 1654 | } |
| 1655 | return(result); |
| 1656 | }//testing possibleHomogPartsInBetween |
| 1657 | |
| 1658 | |
| 1659 | static proc nextSmallerEntry(intvec pmax, intvec pmin, intvec maxDegrees) |
| 1660 | "INPUT: Integer vectors pmax, pmin and maxDegrees. maxDegrees has to have size 2*size(pmax), |
| 1661 | where pmin has to have the same size as pmax. |
| 1662 | OUTPUT: Counting down by lexicographical ordering, this function returns the next smaller |
| 1663 | entry after pmax, which is still bigger than pmin. |
| 1664 | " |
| 1665 | {//nextSmallerEntry |
| 1666 | if (pmax == pmin) |
| 1667 | {return (pmin);} |
| 1668 | if (size(pmax) == 1) |
| 1669 | { |
| 1670 | if (pmax <= pmin) |
| 1671 | {return(pmin);} |
| 1672 | else |
| 1673 | {return(pmax -1);} |
| 1674 | } |
| 1675 | int i; |
| 1676 | intvec recPmax = pmax[1..(size(pmax)-1)]; |
| 1677 | intvec recPmin = pmin[1..(size(pmin)-1)]; |
| 1678 | intvec recMaxDegrees = intvec(maxDegrees[1]); |
| 1679 | for (i = 2; i<=size(maxDegrees); i++) |
| 1680 | { |
| 1681 | if (i!=size(pmax) && i!= size(2*size(pmax))) |
| 1682 | { |
| 1683 | recMaxDegrees = recMaxDegrees,maxDegrees[i]; |
| 1684 | } |
| 1685 | } |
| 1686 | if (recPmax == recPmin) |
| 1687 | {//In this case, we can only possibly count down at our current position |
| 1688 | if (pmax[size(pmax)] > pmin[size(pmin)]) |
| 1689 | {return (recPmax,(pmax[size(pmax)]-1));} |
| 1690 | else |
| 1691 | {return(pmin);} |
| 1692 | }//In this case, we can only possibly count down at our current position |
| 1693 | else |
| 1694 | {//In this case, we can go down to the bounds given by maxDegrees |
| 1695 | if (pmax[size(pmax)] > -maxDegrees[size(pmax)]) |
| 1696 | { |
| 1697 | return (recPmax,(pmax[size(pmax)]-1)); |
| 1698 | } |
| 1699 | else |
| 1700 | { |
| 1701 | return(nextSmallerEntry(recPmax,recPmin,recMaxDegrees),maxDegrees[2*size(pmax)]); |
| 1702 | } |
| 1703 | }//In this case, we can go down to the bounds given by maxDegrees |
| 1704 | }//nextSmallerEntry |
| 1705 | |
| 1706 | |
| 1707 | static proc test_nextSmallerEntry() |
| 1708 | {//testing nextSmallerEntry |
| 1709 | int result = 1; |
| 1710 | //Test 1: one element in intvec |
| 1711 | intvec expected = intvec(2); |
| 1712 | intvec obtained = nextSmallerEntry(intvec(3), |
| 1713 | intvec(2), |
| 1714 | intvec(5,5)); |
| 1715 | if (expected!=obtained) |
| 1716 | { |
| 1717 | print("Test 1 for nextSmallerEntry failed."); |
| 1718 | print("Expected:\n"); |
| 1719 | print(expected); |
| 1720 | print("obtained:\n"); |
| 1721 | print(obtained); |
| 1722 | result = 0; |
| 1723 | } |
| 1724 | //Test 2: more than one element in intvec, no overlap |
| 1725 | expected = intvec(1,1); |
| 1726 | obtained = nextSmallerEntry(intvec(1,2), intvec(1,1), |
| 1727 | intvec(5,5,5,5)); |
| 1728 | if (expected!=obtained) |
| 1729 | { |
| 1730 | print("Test 2 for nextSmallerEntry failed."); |
| 1731 | print("Expected:\n"); |
| 1732 | print(expected); |
| 1733 | print("obtained:\n"); |
| 1734 | print(obtained); |
| 1735 | result = 0; |
| 1736 | } |
| 1737 | //Test 3: More than one element in intvec, overlap |
| 1738 | expected = intvec(1,5); |
| 1739 | obtained = nextSmallerEntry(intvec(2,-5), intvec(1,1), |
| 1740 | intvec(5,5,5,5)); |
| 1741 | if (expected!=obtained) |
| 1742 | { |
| 1743 | print("Test 3 for nextSmallerEntry failed."); |
| 1744 | print("Expected:\n"); |
| 1745 | print(expected); |
| 1746 | print("obtained:\n"); |
| 1747 | print(obtained); |
| 1748 | result = 0; |
| 1749 | } |
| 1750 | //Test 4: More than one element in intvec, more than one overlap |
| 1751 | expected = intvec(1,5,5); |
| 1752 | obtained = nextSmallerEntry(intvec(2,-5,-5), intvec(1,1,1), |
| 1753 | intvec(5,5,5,5,5,5)); |
| 1754 | if (expected!=obtained) |
| 1755 | { |
| 1756 | print("Test 4 for nextSmallerEntry failed."); |
| 1757 | print("Expected:\n"); |
| 1758 | print(expected); |
| 1759 | print("obtained:\n"); |
| 1760 | print(obtained); |
| 1761 | result = 0; |
| 1762 | } |
| 1763 | return(result); |
| 1764 | }//testing nextSmallerEntry |
| 1765 | |
| 1766 | |
| 1767 | static proc possibleHomogPartsInBetweenNonRecursive(intvec pmax, intvec pmin, intvec maxDegrees) |
| 1768 | " |
| 1769 | INPUT: Integer vectors pmax and maxDegrees. All but maxDegrees are of the same size, |
| 1770 | except from maxDegrees, which is double of the size of the rest. |
| 1771 | OUTPUT: A list of possible points in Z^n that can lie between pmax and |
| 1772 | pmin, sorted with respect to the lexicographic order from |
| 1773 | biggest to smallest (leftmost entry in the intvec is the biggest), |
| 1774 | represented as list of intvecs. |
| 1775 | " |
| 1776 | {//possibleHomogPartsInBetween |
| 1777 | if (size(pmax) != size(pmin) || 2*size(pmax)!=size(maxDegrees) || pmax<=pmin) |
| 1778 | { |
| 1779 | ERROR("pmax and pmin shall have the same size, and maxDegrees |
| 1780 | shall be double the size of both. Furhtermore, it must hold that pmax>pmin. The |
| 1781 | Input was: " + string(pmax) + ", " + string(pmin) + ", " + string(maxDegrees)); |
| 1782 | } |
| 1783 | list result = list(pmax); |
| 1784 | int pos; int i; int j; int k; |
| 1785 | list leftPart; |
| 1786 | int leftPartIsMaxAndMin; |
| 1787 | list possibleMiddles; |
| 1788 | list possibleRightParts = list(list()); |
| 1789 | list tempRightParts; |
| 1790 | intvec tempentry; |
| 1791 | for (pos = size(pmax); pos >=1 ; pos--) |
| 1792 | { |
| 1793 | leftPart = list(); |
| 1794 | leftPartIsMaxAndMin = 1; |
| 1795 | possibleMiddles = list(); |
| 1796 | for (i = 1; i < pos; i++) |
| 1797 | {//filling the left part |
| 1798 | leftPart[i] = pmax[i]; |
| 1799 | if(pmax[i]!=pmin[i]) |
| 1800 | {leftPartIsMaxAndMin = 0;} |
| 1801 | }//filling the left part |
| 1802 | if (leftPartIsMaxAndMin) |
| 1803 | { |
| 1804 | for (i = pmax[pos]-1; i>pmin[pos]; i--) |
| 1805 | {//possible entries for position pos |
| 1806 | possibleMiddles = possibleMiddles + list(i); |
| 1807 | }//possible entries for position pos |
| 1808 | } |
| 1809 | else |
| 1810 | { |
| 1811 | for (i = pmax[pos]-1; i>=-maxDegrees[pos]; i--) |
| 1812 | {//possible entries for position pos |
| 1813 | possibleMiddles = possibleMiddles + list(i); |
| 1814 | }//possible entries for position pos |
| 1815 | } |
| 1816 | for (i = 1; i<=size(possibleMiddles); i++) |
| 1817 | {//Adding possibilities to result |
| 1818 | for (j = 1; j<=size(possibleRightParts); j++) |
| 1819 | {//going through the right parts |
| 1820 | tempentry = intvec(0); |
| 1821 | for (k = 1; k<=size(leftPart);k++) |
| 1822 | { |
| 1823 | tempentry[k] = leftPart[k]; |
| 1824 | } |
| 1825 | if (size(leftPart)==0) |
| 1826 | {tempentry = possibleMiddles[i];} |
| 1827 | else |
| 1828 | {tempentry = tempentry,possibleMiddles[i];} |
| 1829 | for (k = 1; k<=size(possibleRightParts[j]) ; k++) |
| 1830 | { |
| 1831 | tempentry = tempentry, possibleRightParts[j][k]; |
| 1832 | } |
| 1833 | result = result + list(tempentry); |
| 1834 | }//going through the right parts |
| 1835 | }//Adding possibilities to result |
| 1836 | tempRightParts = list(); |
| 1837 | for (i = 1; i<=size(possibleRightParts);i++) |
| 1838 | { |
| 1839 | for (j = -maxDegrees[pos]; j <= maxDegrees[pos + size(pmax)]; |
| 1840 | j++) |
| 1841 | { |
| 1842 | tempRightParts = tempRightParts + list(list(j) + possibleRightParts[i]); |
| 1843 | } |
| 1844 | } |
| 1845 | possibleRightParts = tempRightParts; |
| 1846 | } |
| 1847 | //Now the last possible guys |
| 1848 | result = result + list(pmin); |
| 1849 | leftPart = list(); |
| 1850 | int positionWhereDifference = 1; |
| 1851 | for (i = 1; i<= size(pmin); i++) |
| 1852 | { |
| 1853 | if(pmax[i] != pmin[i]) |
| 1854 | { |
| 1855 | positionWhereDifference = i; |
| 1856 | break; |
| 1857 | } |
| 1858 | } |
| 1859 | possibleRightParts = list(list()); |
| 1860 | for (pos = size(pmin); pos > positionWhereDifference; pos--) |
| 1861 | {//Dealing with the minimal parts that we left out in the loop above |
| 1862 | leftPart = list(); |
| 1863 | possibleMiddles = list(); |
| 1864 | for (i = 1; i < pos; i++) |
| 1865 | {//filling up the left part |
| 1866 | leftPart[i] = pmin[i]; |
| 1867 | }//filling up the left part |
| 1868 | for (i = pmin[pos] +1 ; i<=maxDegrees[pos + size(pmin)] ; i++) |
| 1869 | { |
| 1870 | possibleMiddles = possibleMiddles + list(i); |
| 1871 | } |
| 1872 | for (i = 1; i<=size(possibleMiddles); i++) |
| 1873 | {//Adding possibilities to result |
| 1874 | for (j = 1; j<=size(possibleRightParts); j++) |
| 1875 | {//going through the right parts |
| 1876 | tempentry = intvec(0); |
| 1877 | for (k = 1; k<=size(leftPart);k++) |
| 1878 | { |
| 1879 | tempentry[k] = leftPart[k]; |
| 1880 | } |
| 1881 | if (size(leftPart)==0) |
| 1882 | {tempentry = possibleMiddles[i];} |
| 1883 | else |
| 1884 | {tempentry = tempentry,possibleMiddles[i];} |
| 1885 | for (k = 1; k<=size(possibleRightParts[j]) ; k++) |
| 1886 | { |
| 1887 | tempentry = tempentry, possibleRightParts[j][k]; |
| 1888 | } |
| 1889 | result = result + list(tempentry); |
| 1890 | }//going through the right parts |
| 1891 | }//Adding possibilities to result |
| 1892 | tempRightParts = list(); |
| 1893 | for (i = 1; i<=size(possibleRightParts);i++) |
| 1894 | { |
| 1895 | for (j = -maxDegrees[pos]; j <= maxDegrees[pos + size(pmax)]; |
| 1896 | j++) |
| 1897 | { |
| 1898 | tempRightParts = tempRightParts + list(list(j) + possibleRightParts[i]); |
| 1899 | } |
| 1900 | } |
| 1901 | possibleRightParts = tempRightParts; |
| 1902 | }//Dealing with the minimal parts that we left out in the loop above |
| 1903 | result = sort(result)[1]; |
| 1904 | if (result[1] != pmin) |
| 1905 | {result = insert(result,pmin);} |
| 1906 | return(result); |
| 1907 | }//possibleHomogPartsInBetween |
| 1908 | |
| 1909 | |
| 1910 | static proc test_possibleHomogPartsInBetweenNonRecursive() |
| 1911 | {//testing possibleHomogPartsInBetweenNonRecursive |
| 1912 | int result = 1; |
| 1913 | //Test 1: Nothing in between |
| 1914 | list expected = list(intvec(1,1),intvec(1,2)); |
| 1915 | list obtained = |
| 1916 | possibleHomogPartsInBetweenNonRecursive(intvec(1,2), |
| 1917 | intvec(1,1), |
| 1918 | intvec(10,10,10,10)); |
| 1919 | if (!isListEqual(expected, obtained)) |
| 1920 | { |
| 1921 | print("Test 1 for possibleHomogPartsInBetweenNonRecursive failed."); |
| 1922 | print("Expected:\n"); |
| 1923 | print(expected); |
| 1924 | print("obtained:\n"); |
| 1925 | print(obtained); |
| 1926 | result = 0; |
| 1927 | } |
| 1928 | //Test 2: exactly one intvec in between |
| 1929 | expected = list(intvec(1,1),intvec(1,2),intvec(1,3)); |
| 1930 | obtained = |
| 1931 | possibleHomogPartsInBetweenNonRecursive(intvec(1,3), |
| 1932 | intvec(1,1), |
| 1933 | intvec(10,10,10,10)); |
| 1934 | if (!isListEqual(expected, obtained)) |
| 1935 | { |
| 1936 | print("Test 2 for possibleHomogPartsInBetweenNonRecursive failed."); |
| 1937 | print("Expected:\n"); |
| 1938 | print(expected); |
| 1939 | print("obtained:\n"); |
| 1940 | print(obtained); |
| 1941 | result = 0; |
| 1942 | } |
| 1943 | //Test 3: One complete degree of freedom |
| 1944 | expected = list(intvec(1,1,1), |
| 1945 | intvec(1,1,2), |
| 1946 | intvec(1,1,3), |
| 1947 | intvec(1,1,4), |
| 1948 | intvec(1,1,5), |
| 1949 | intvec(1,2,-5), |
| 1950 | intvec(1,2,-4), |
| 1951 | intvec(1,2,-3), |
| 1952 | intvec(1,2,-2), |
| 1953 | intvec(1,2,-1), |
| 1954 | intvec(1,2,0), |
| 1955 | intvec(1,2,1), |
| 1956 | intvec(1,2,2), |
| 1957 | intvec(1,2,3), |
| 1958 | intvec(1,2,4), |
| 1959 | intvec(1,2,5), |
| 1960 | intvec(1,3,-5), |
| 1961 | intvec(1,3,-4), |
| 1962 | intvec(1,3,-3), |
| 1963 | intvec(1,3,-2), |
| 1964 | intvec(1,3,-1), |
| 1965 | intvec(1,3,0), |
| 1966 | intvec(1,3,1), |
| 1967 | intvec(1,3,2), |
| 1968 | intvec(1,3,3), |
| 1969 | intvec(1,3,4), |
| 1970 | intvec(1,3,5)); |
| 1971 | obtained = |
| 1972 | possibleHomogPartsInBetweenNonRecursive(intvec(1,3,5), |
| 1973 | intvec(1,1,1), |
| 1974 | intvec(5,5,5,5,5,5)); |
| 1975 | if (!isListEqual(expected, obtained)) |
| 1976 | { |
| 1977 | print("Test 3 for possibleHomogPartsInBetweenNonRecursive failed."); |
| 1978 | print("Expected:\n"); |
| 1979 | print(expected); |
| 1980 | print("obtained:\n"); |
| 1981 | print(obtained); |
| 1982 | result = 0; |
| 1983 | } |
| 1984 | return(result); |
| 1985 | }//testing possibleHomogPartsInBetweenNonRecursive |
| 1986 | |
| 1987 | |
| 1988 | static proc increment_intvec(intvec v, intvec maxDegInCoordinates) |
| 1989 | "USAGE: increment_intvec(v,maxDegInCoordinates); v and |
| 1990 | maxDegInCoordinates are both intvecs. |
| 1991 | RETURN: intvec |
| 1992 | PURPOSE: Increments the intvec v, assuming that each coordinate has |
| 1993 | maximal entry as given in the respective position in |
| 1994 | maxDegInCoordinates. |
| 1995 | ASSUMPTIONS: |
| 1996 | - v and maxDegInCoordinates have the same size. |
| 1997 | "{//increment_intvec |
| 1998 | intvec result = v; |
| 1999 | int i; |
| 2000 | for (i = size(result); i>0; i--) |
| 2001 | {//going through the positions |
| 2002 | if (result[i] >= maxDegInCoordinates[i]) |
| 2003 | {//need to go to different position |
| 2004 | if (i == 1) |
| 2005 | {//max position already reached; i.e. max vector |
| 2006 | return(v); |
| 2007 | }//max position already reached; i.e. max vector |
| 2008 | result[i] = 0; |
| 2009 | }//need to go to different position |
| 2010 | else |
| 2011 | {//just change counter at that position and done |
| 2012 | result[i]= result[i]+1; |
| 2013 | break; |
| 2014 | }//just change counter at that position and done |
| 2015 | }//going through the positions |
| 2016 | return(result); |
| 2017 | }//increment_intvec |
| 2018 | |
| 2019 | |
| 2020 | static proc test_increment_intvec() |
| 2021 | {//testing increment_intvec |
| 2022 | int result = 1; |
| 2023 | //Test 1: one element in intvec |
| 2024 | intvec expected = intvec(4); |
| 2025 | intvec obtained = increment_intvec(intvec(3), |
| 2026 | intvec(5)); |
| 2027 | if (expected!=obtained) |
| 2028 | { |
| 2029 | print("Test 1 for increment_intvec failed."); |
| 2030 | print("Expected:\n"); |
| 2031 | print(expected); |
| 2032 | print("obtained:\n"); |
| 2033 | print(obtained); |
| 2034 | result = 0; |
| 2035 | } |
| 2036 | //Test 2: more than one element in intvec, no overlap |
| 2037 | expected = intvec(1,3); |
| 2038 | obtained = increment_intvec(intvec(1,2),intvec(5,5)); |
| 2039 | if (expected!=obtained) |
| 2040 | { |
| 2041 | print("Test 2 for increment_intvec failed."); |
| 2042 | print("Expected:\n"); |
| 2043 | print(expected); |
| 2044 | print("obtained:\n"); |
| 2045 | print(obtained); |
| 2046 | result = 0; |
| 2047 | } |
| 2048 | //Test 3: More than one element in intvec, overlap |
| 2049 | expected = intvec(3,0); |
| 2050 | obtained = increment_intvec(intvec(2,5), |
| 2051 | intvec(5,5)); |
| 2052 | if (expected!=obtained) |
| 2053 | { |
| 2054 | print("Test 3 for increment_intvec failed."); |
| 2055 | print("Expected:\n"); |
| 2056 | print(expected); |
| 2057 | print("obtained:\n"); |
| 2058 | print(obtained); |
| 2059 | result = 0; |
| 2060 | } |
| 2061 | //Test 4: More than one element in intvec, more than one overlap |
| 2062 | expected = intvec(3,0,0); |
| 2063 | obtained = increment_intvec(intvec(2,5,5), |
| 2064 | intvec(5,5,5)); |
| 2065 | if (expected!=obtained) |
| 2066 | { |
| 2067 | print("Test 4 for increment_intvec failed."); |
| 2068 | print("Expected:\n"); |
| 2069 | print(expected); |
| 2070 | print("obtained:\n"); |
| 2071 | print(obtained); |
| 2072 | result = 0; |
| 2073 | } |
| 2074 | return(result); |
| 2075 | }//testing increment_intvec |
| 2076 | |
| 2077 | |
| 2078 | //I know that Singular has this function in the package |
| 2079 | //qhmoduli.lib. But I don't see the reason why I should clutter my |
| 2080 | //namespace with functions to study Moduli Spaces of |
| 2081 | //Semi-Quasihomogeneous Singularities (in case somebody wonders) |
| 2082 | static proc Min(def lst) |
| 2083 | "USAGE: Min(lst); list is an iterable element (list/ideal/intvec) |
| 2084 | containing ordered elements. |
| 2085 | PURPOSE: returns the minimal element in lst |
| 2086 | ASSUME: lst contains at least one element |
| 2087 | "{//proc Min |
| 2088 | def minElem = lst[1]; |
| 2089 | int i; |
| 2090 | for (i = 2; i<=size(lst);i++) |
| 2091 | { |
| 2092 | if (lst[i]<minElem) |
| 2093 | { |
| 2094 | minElem = lst[i]; |
| 2095 | } |
| 2096 | } |
| 2097 | return (minElem); |
| 2098 | }//proc Min |
| 2099 | |
| 2100 | |
| 2101 | static proc test_Min() |
| 2102 | {//Testing Min |
| 2103 | int result = 1; |
| 2104 | //Test 1: One element list |
| 2105 | int expected= 1; |
| 2106 | int obtained = Min(list(1)); |
| 2107 | if (expected!=obtained) |
| 2108 | { |
| 2109 | print("Test 1 for Min failed."); |
| 2110 | print("Expected:\n"); |
| 2111 | print(expected); |
| 2112 | print("obtained:\n"); |
| 2113 | print(obtained); |
| 2114 | result = 0; |
| 2115 | } |
| 2116 | //Test 2: Two element list, first one is Min |
| 2117 | expected = 5; |
| 2118 | obtained = Min(list(5,8)); |
| 2119 | if (expected!=obtained) |
| 2120 | { |
| 2121 | print("Test 2 for Min failed."); |
| 2122 | print("Expected:\n"); |
| 2123 | print(expected); |
| 2124 | print("obtained:\n"); |
| 2125 | print(obtained); |
| 2126 | result = 0; |
| 2127 | } |
| 2128 | //Test 3: Two element list, second one is Min |
| 2129 | expected = 5; |
| 2130 | obtained = Min(list(8,5)); |
| 2131 | if (expected!=obtained) |
| 2132 | { |
| 2133 | print("Test 3 for Min failed."); |
| 2134 | print("Expected:\n"); |
| 2135 | print(expected); |
| 2136 | print("obtained:\n"); |
| 2137 | print(obtained); |
| 2138 | result = 0; |
| 2139 | } |
| 2140 | //Test 4: A lot of elements, Min randomly in between. |
| 2141 | expected = -11; |
| 2142 | obtained = Min(list(5,8,7,2,8,0,-11,0,25)); |
| 2143 | if (expected!=obtained) |
| 2144 | { |
| 2145 | print("Test 4 for Min failed."); |
| 2146 | print("Expected:\n"); |
| 2147 | print(expected); |
| 2148 | print("obtained:\n"); |
| 2149 | print(obtained); |
| 2150 | result = 0; |
| 2151 | } |
| 2152 | return(result); |
| 2153 | }//Testing Min |
| 2154 | |
| 2155 | |
| 2156 | static proc isListEqual(list l1, list l2) |
| 2157 | "USAGE: isListEq(l1,l2); l1 and l2 are arbitrary lists. |
| 2158 | PURPOSE: returns if l1 and l2 contain the same elements |
| 2159 | ASSUME: every non-list element in l1 and l2 can be compared with the |
| 2160 | == operator |
| 2161 | "{ |
| 2162 | if (size(l1)!=size(l2)) |
| 2163 | {return(0);} |
| 2164 | int i; |
| 2165 | for (i = 1; i<=size(l1);i++) |
| 2166 | { |
| 2167 | if (typeof(l1[i])!=typeof(l2[i])) |
| 2168 | { return (0); } |
| 2169 | if (typeof(l1[i])=="list") |
| 2170 | { |
| 2171 | if (!isListEqual(l1[i],l2[i])) |
| 2172 | { |
| 2173 | return(0); |
| 2174 | } |
| 2175 | } |
| 2176 | else |
| 2177 | { |
| 2178 | if (l1[i]!=l2[i]) |
| 2179 | {return(0);} |
| 2180 | } |
| 2181 | } |
| 2182 | return(1); |
| 2183 | } |
| 2184 | |
| 2185 | static proc test_isListEqual() |
| 2186 | { |
| 2187 | int result = 1; |
| 2188 | //Test 1: empty list and empty list |
| 2189 | int expected = 1; |
| 2190 | list input1 = list(); |
| 2191 | list input2 = list(); |
| 2192 | int obtained = isListEqual(input1,input2); |
| 2193 | if (expected !=obtained) |
| 2194 | { |
| 2195 | print("Test 1 for isListEqual failed."); |
| 2196 | print("Expected:\n"); |
| 2197 | print(expected); |
| 2198 | print("obtained:\n"); |
| 2199 | print(obtained); |
| 2200 | result = 0; |
| 2201 | } |
| 2202 | //Test 2: empty list and non-empty list |
| 2203 | expected = 0; |
| 2204 | input1 = list(); |
| 2205 | input2 = list(list(),1,3,4); |
| 2206 | obtained = isListEqual(input1,input2); |
| 2207 | if (expected !=obtained) |
| 2208 | { |
| 2209 | print("Test 2 for isListEqual failed."); |
| 2210 | print("Expected:\n"); |
| 2211 | print(expected); |
| 2212 | print("obtained:\n"); |
| 2213 | print(obtained); |
| 2214 | result = 0; |
| 2215 | } |
| 2216 | //Test 3: non-empty list and empty list |
| 2217 | expected = 0; |
| 2218 | input2 = list(); |
| 2219 | input1 = list(list(),1,3,4); |
| 2220 | obtained = isListEqual(input1,input2); |
| 2221 | if (expected !=obtained) |
| 2222 | { |
| 2223 | print("Test 3 for isListEqual failed."); |
| 2224 | print("Expected:\n"); |
| 2225 | print(expected); |
| 2226 | print("obtained:\n"); |
| 2227 | print(obtained); |
| 2228 | result = 0; |
| 2229 | } |
| 2230 | //Test 4: lists with entries of the same type, equal |
| 2231 | expected = 1; |
| 2232 | input1 = list(1,2,3,4); |
| 2233 | input2 = list(1,2,3,4); |
| 2234 | obtained = isListEqual(input1,input2); |
| 2235 | if (expected !=obtained) |
| 2236 | { |
| 2237 | print("Test 4 for isListEqual failed."); |
| 2238 | print("Expected:\n"); |
| 2239 | print(expected); |
| 2240 | print("obtained:\n"); |
| 2241 | print(obtained); |
| 2242 | result = 0; |
| 2243 | } |
| 2244 | //Test 5: lists with entries of the same type, not equal |
| 2245 | expected = 0; |
| 2246 | input1 = list(4,3,2,1); |
| 2247 | input2 = list(1,2,3,4); |
| 2248 | obtained = isListEqual(input1,input2); |
| 2249 | if (expected !=obtained) |
| 2250 | { |
| 2251 | print("Test 5 for isListEqual failed."); |
| 2252 | print("Expected:\n"); |
| 2253 | print(expected); |
| 2254 | print("obtained:\n"); |
| 2255 | print(obtained); |
| 2256 | result = 0; |
| 2257 | } |
| 2258 | //Test 6: lists with entries of the different types, equal |
| 2259 | expected = 1; |
| 2260 | input1 = list(4,intvec(3,2),list(list()),1); |
| 2261 | input2 = list(4,intvec(3,2),list(list()),1); |
| 2262 | obtained = isListEqual(input1,input2); |
| 2263 | if (expected !=obtained) |
| 2264 | { |
| 2265 | print("Test 6 for isListEqual failed."); |
| 2266 | print("Expected:\n"); |
| 2267 | print(expected); |
| 2268 | print("obtained:\n"); |
| 2269 | print(obtained); |
| 2270 | result = 0; |
| 2271 | } |
| 2272 | //Test 7: lists with entries of the different types, not equal |
| 2273 | expected = 0; |
| 2274 | input1 = list(4,intvec(3,2),list(),1); |
| 2275 | input2 = list(4,intvec(3,2),list(list()),1); |
| 2276 | obtained = isListEqual(input1,input2); |
| 2277 | if (expected !=obtained) |
| 2278 | { |
| 2279 | print("Test 7 for isListEqual failed."); |
| 2280 | print("Expected:\n"); |
| 2281 | print(expected); |
| 2282 | print("obtained:\n"); |
| 2283 | print(obtained); |
| 2284 | result = 0; |
| 2285 | } |
| 2286 | return(result); |
| 2287 | } |
| 2288 | |
| 2289 | ////////////////////////////////////////////////// |
| 2290 | //*********RING HANDLING HELPER FUNCTIONS********* |
| 2291 | ////////////////////////////////////////////////// |
| 2292 | |
420 | | //================================================== |
| 3027 | |
| 3028 | static proc test_ncfactor_isShift() |
| 3029 | {//testing ncfactor_isShift |
| 3030 | int result = 1; |
| 3031 | int i; int j; int k; |
| 3032 | //Test 1: Shift with no surprises |
| 3033 | ring R = 0,(n,s),dp; |
| 3034 | def r = nc_algebra(1,s); |
| 3035 | setring r; |
| 3036 | int expected = 1; |
| 3037 | int obtained = ncfactor_isShift(); |
| 3038 | if (expected !=obtained) |
| 3039 | { |
| 3040 | print("Test 1 for ncfactor_isShift failed."); |
| 3041 | print("Expected:\n"); |
| 3042 | print(expected); |
| 3043 | print("obtained:\n"); |
| 3044 | print(obtained); |
| 3045 | result = 0; |
| 3046 | } |
| 3047 | kill R; |
| 3048 | kill r; |
| 3049 | //Test 2: Shift with reversed parameters |
| 3050 | ring R = 0,(n,s),dp; |
| 3051 | def r = nc_algebra(1,-n); |
| 3052 | setring r; |
| 3053 | expected = 1; |
| 3054 | obtained = ncfactor_isShift(); |
| 3055 | if (expected !=obtained) |
| 3056 | { |
| 3057 | print("Test 2 for ncfactor_isShift failed."); |
| 3058 | print("Expected:\n"); |
| 3059 | print(expected); |
| 3060 | print("obtained:\n"); |
| 3061 | print(obtained); |
| 3062 | result = 0; |
| 3063 | } |
| 3064 | kill R; kill r; |
| 3065 | //Test 3: All possibilities of the third shift algebra. |
| 3066 | for(i=1;i<=6;i++) |
| 3067 | { |
| 3068 | ring R3 = 0,(x,y,z,s1,s2,s3),dp; |
| 3069 | matrix D[6][6]; |
| 3070 | list perms = list(list(list(s1,0,0,0,0,0), |
| 3071 | list(0,s2,0,0,0,0), |
| 3072 | list(0,0,s3,0,0,0)), |
| 3073 | list(list(s1,0,0,0,0,0), |
| 3074 | list(0,0,s2,0,0,0), |
| 3075 | list(0,s3,0,0,0,0)), |
| 3076 | list(list(0,s1,0,0,0,0), |
| 3077 | list(s2,0,0,0,0,0), |
| 3078 | list(0,0,s3,0,0,0)), |
| 3079 | list(list(0,s1,0,0,0,0), |
| 3080 | list(0,0,s2,0,0,0), |
| 3081 | list(s3,0,0,0,0,0)), |
| 3082 | list(list(0,0,s1,0,0,0), |
| 3083 | list(0,s2,0,0,0,0), |
| 3084 | list(s3,0,0,0,0,0)), |
| 3085 | list(list(0,0,s1,0,0,0), |
| 3086 | list(s2,0,0,0,0,0), |
| 3087 | list(0,s3,0,0,0,0))); |
| 3088 | for (j=1;j<=size(perms[i]);j++) |
| 3089 | { |
| 3090 | for (k=1;k<=size(perms[i][j]);k++) |
| 3091 | { |
| 3092 | D[k,3+j]=perms[i][j][k]; |
| 3093 | } |
| 3094 | } |
| 3095 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3096 | 1,1,1,1,1,1, |
| 3097 | 1,1,1,1,1,1, |
| 3098 | 1,1,1,1,1,1, |
| 3099 | 1,1,1,1,1,1, |
| 3100 | 1,1,1,1,1,1; |
| 3101 | def r3 = nc_algebra(C,D); |
| 3102 | setring(r3); |
| 3103 | expected = 1; |
| 3104 | obtained = ncfactor_isShift(); |
| 3105 | if (expected !=obtained) |
| 3106 | { |
| 3107 | print("Test 3 for ncfactor_isShift failed. Basering:"); |
| 3108 | basering; |
| 3109 | print("Expected:\n"); |
| 3110 | print(expected); |
| 3111 | print("obtained:\n"); |
| 3112 | print(obtained); |
| 3113 | result = 0; |
| 3114 | } |
| 3115 | kill r3; |
| 3116 | kill R3; |
| 3117 | } |
| 3118 | //test 4: All possibilities for third shift algebra with reversed parameters. |
| 3119 | for(i=1;i<=6;i++) |
| 3120 | { |
| 3121 | ring R3 = 0,(x,y,z,s1,s2,s3),dp; |
| 3122 | matrix D[6][6]; |
| 3123 | list perms = list(list(list(-x,0,0,0,0,0), |
| 3124 | list(0,-y,0,0,0,0), |
| 3125 | list(0,0,-z,0,0,0)), |
| 3126 | list(list(-x,0,0,0,0,0), |
| 3127 | list(0,0,-z,0,0,0), |
| 3128 | list(0,-y,0,0,0,0)), |
| 3129 | list(list(0,-y,0,0,0,0), |
| 3130 | list(-x,0,0,0,0,0), |
| 3131 | list(0,0,-z,0,0,0)), |
| 3132 | list(list(0,-y,0,0,0,0), |
| 3133 | list(0,0,-z,0,0,0), |
| 3134 | list(-x,0,0,0,0,0)), |
| 3135 | list(list(0,0,-z,0,0,0), |
| 3136 | list(0,-y,0,0,0,0), |
| 3137 | list(-x,0,0,0,0,0)), |
| 3138 | list(list(0,0,-z,0,0,0), |
| 3139 | list(-x,0,0,0,0,0), |
| 3140 | list(0,-y,0,0,0,0))); |
| 3141 | for (j=1;j<=size(perms[i]);j++) |
| 3142 | { |
| 3143 | for (k=1;k<=size(perms[i][j]);k++) |
| 3144 | { |
| 3145 | D[k,3+j]=perms[i][j][k]; |
| 3146 | } |
| 3147 | } |
| 3148 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3149 | 1,1,1,1,1,1, |
| 3150 | 1,1,1,1,1,1, |
| 3151 | 1,1,1,1,1,1, |
| 3152 | 1,1,1,1,1,1, |
| 3153 | 1,1,1,1,1,1; |
| 3154 | def r3 = nc_algebra(C,D); |
| 3155 | setring(r3); |
| 3156 | expected = 1; |
| 3157 | obtained = ncfactor_isShift(); |
| 3158 | if (expected !=obtained) |
| 3159 | { |
| 3160 | print("Test 4 for ncfactor_isShift failed. Basering:"); |
| 3161 | basering; |
| 3162 | print("Expected:\n"); |
| 3163 | print(expected); |
| 3164 | print("obtained:\n"); |
| 3165 | print(obtained); |
| 3166 | result = 0; |
| 3167 | } |
| 3168 | kill r3; |
| 3169 | kill R3; |
| 3170 | } |
| 3171 | //Test 5: subshift, but not shift |
| 3172 | ring R = 0,(x,y,z),dp; |
| 3173 | matrix C[3][3] = 1,1,1,1,1,1,1,1,1; |
| 3174 | matrix D[3][3] = 0,0,0, |
| 3175 | 0,0,z, |
| 3176 | 0,0,0; |
| 3177 | def r = nc_algebra(C,D); |
| 3178 | setring(r); |
| 3179 | expected = 0; |
| 3180 | obtained = ncfactor_isShift(); |
| 3181 | if (expected !=obtained) |
| 3182 | { |
| 3183 | print("Test 5 for ncfactor_isShift failed. Basering:"); |
| 3184 | basering; |
| 3185 | print("Expected:\n"); |
| 3186 | print(expected); |
| 3187 | print("obtained:\n"); |
| 3188 | print(obtained); |
| 3189 | result = 0; |
| 3190 | } |
| 3191 | kill R; kill r; |
| 3192 | //Test 6: Commutative ring |
| 3193 | ring R = 0,(n,sn),dp; |
| 3194 | expected = 0; |
| 3195 | obtained = ncfactor_isShift(); |
| 3196 | if (expected !=obtained) |
| 3197 | { |
| 3198 | print("Test 6 for ncfactor_isShift failed. Basering:"); |
| 3199 | basering; |
| 3200 | print("Expected:\n"); |
| 3201 | print(expected); |
| 3202 | print("obtained:\n"); |
| 3203 | print(obtained); |
| 3204 | result = 0; |
| 3205 | } |
| 3206 | kill R; |
| 3207 | return(result); |
| 3208 | }//testing ncfactor_isShift |
| 3209 | |
| 3210 | |
| 3211 | static proc checkIfProperNthShift() |
| 3212 | " |
| 3213 | INPUT: None |
| 3214 | OUTPUT: Checks whether the given basering is a proper shift algebra. |
| 3215 | Proper means in the sense of our algorithms, i.e. fulfilling |
| 3216 | the assumption that our basering is the Nth shift algebra and |
| 3217 | that the xs are the first n variables, the shift |
| 3218 | operators are the last n. Returns 1 if proper, 0 otherwise. |
| 3219 | " |
| 3220 | {//checkIfProperNthShift |
| 3221 | if (!ncfactor_isShift()) |
| 3222 | {return(0);} |
| 3223 | int i; |
| 3224 | for (i = 1; i<=nvars(basering) div 2; i++) |
| 3225 | { |
| 3226 | if (var(i + nvars(basering) div 2)*var(i) |
| 3227 | - var(i)*var(i+nvars(basering) div 2)!=var(i+nvars(basering) div 2)) |
| 3228 | { |
| 3229 | return(0); |
| 3230 | } |
| 3231 | } |
| 3232 | return(1); |
| 3233 | }//checkIfProperNthShift |
| 3234 | |
| 3235 | |
| 3236 | static proc test_checkIfProperNthShift() |
| 3237 | {//testing checkIfProperNthShift |
| 3238 | int result = 1; |
| 3239 | int i; int j; int k; |
| 3240 | //Test 1: Shift with no surprises |
| 3241 | ring R = 0,(n,s),dp; |
| 3242 | def r = nc_algebra(1,s); |
| 3243 | setring r; |
| 3244 | int expected = 1; |
| 3245 | int obtained = checkIfProperNthShift(); |
| 3246 | if (expected !=obtained) |
| 3247 | { |
| 3248 | print("Test 1 for checkIfProperNthShift failed."); |
| 3249 | print("Expected:\n"); |
| 3250 | print(expected); |
| 3251 | print("obtained:\n"); |
| 3252 | print(obtained); |
| 3253 | result = 0; |
| 3254 | } |
| 3255 | kill R; |
| 3256 | kill r; |
| 3257 | //Test 2: Shift with reversed parameters |
| 3258 | ring R = 0,(n,s),dp; |
| 3259 | def r = nc_algebra(1,-n); |
| 3260 | setring r; |
| 3261 | expected = 0; |
| 3262 | obtained = checkIfProperNthShift(); |
| 3263 | if (expected !=obtained) |
| 3264 | { |
| 3265 | print("Test 2 for checkIfProperNthShift failed."); |
| 3266 | print("Expected:\n"); |
| 3267 | print(expected); |
| 3268 | print("obtained:\n"); |
| 3269 | print(obtained); |
| 3270 | result = 0; |
| 3271 | } |
| 3272 | kill R; kill r; |
| 3273 | //Test 3: All possibilities of the third shift algebra, that are not |
| 3274 | //valid. |
| 3275 | for(i=1;i<=5;i++) |
| 3276 | { |
| 3277 | ring R3 = 0,(x,y,z,s1,s2,s3),dp; |
| 3278 | matrix D[6][6]; |
| 3279 | list perms = list(list(list(s1,0,0,0,0,0), |
| 3280 | list(0,0,s2,0,0,0), |
| 3281 | list(0,s3,0,0,0,0)), |
| 3282 | list(list(0,s1,0,0,0,0), |
| 3283 | list(s2,0,0,0,0,0), |
| 3284 | list(0,0,s3,0,0,0)), |
| 3285 | list(list(0,s1,0,0,0,0), |
| 3286 | list(0,0,s2,0,0,0), |
| 3287 | list(s3,0,0,0,0,0)), |
| 3288 | list(list(0,0,s1,0,0,0), |
| 3289 | list(0,s2,0,0,0,0), |
| 3290 | list(s3,0,0,0,0,0)), |
| 3291 | list(list(0,0,s1,0,0,0), |
| 3292 | list(s2,0,0,0,0,0), |
| 3293 | list(0,s3,0,0,0,0))); |
| 3294 | for (j=1;j<=size(perms[i]);j++) |
| 3295 | { |
| 3296 | for (k=1;k<=size(perms[i][j]);k++) |
| 3297 | { |
| 3298 | D[k,3+j]=perms[i][j][k]; |
| 3299 | } |
| 3300 | } |
| 3301 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3302 | 1,1,1,1,1,1, |
| 3303 | 1,1,1,1,1,1, |
| 3304 | 1,1,1,1,1,1, |
| 3305 | 1,1,1,1,1,1, |
| 3306 | 1,1,1,1,1,1; |
| 3307 | def r3 = nc_algebra(C,D); |
| 3308 | setring(r3); |
| 3309 | expected = 0; |
| 3310 | obtained = checkIfProperNthShift(); |
| 3311 | if (expected !=obtained) |
| 3312 | { |
| 3313 | print("Test 3 for checkIfProperNthShift failed. Basering:"); |
| 3314 | basering; |
| 3315 | print("Expected:\n"); |
| 3316 | print(expected); |
| 3317 | print("obtained:\n"); |
| 3318 | print(obtained); |
| 3319 | result = 0; |
| 3320 | } |
| 3321 | kill r3; |
| 3322 | kill R3; |
| 3323 | } |
| 3324 | //test 4: All possibilities for third shift algebra with reversed parameters. |
| 3325 | for(i=1;i<=6;i++) |
| 3326 | { |
| 3327 | ring R3 = 0,(x,y,z,s1,s2,s3),dp; |
| 3328 | matrix D[6][6]; |
| 3329 | list perms = list(list(list(-x,0,0,0,0,0), |
| 3330 | list(0,-y,0,0,0,0), |
| 3331 | list(0,0,-z,0,0,0)), |
| 3332 | list(list(-x,0,0,0,0,0), |
| 3333 | list(0,0,-z,0,0,0), |
| 3334 | list(0,-y,0,0,0,0)), |
| 3335 | list(list(0,-y,0,0,0,0), |
| 3336 | list(-x,0,0,0,0,0), |
| 3337 | list(0,0,-z,0,0,0)), |
| 3338 | list(list(0,-y,0,0,0,0), |
| 3339 | list(0,0,-z,0,0,0), |
| 3340 | list(-x,0,0,0,0,0)), |
| 3341 | list(list(0,0,-z,0,0,0), |
| 3342 | list(0,-y,0,0,0,0), |
| 3343 | list(-x,0,0,0,0,0)), |
| 3344 | list(list(0,0,-z,0,0,0), |
| 3345 | list(-x,0,0,0,0,0), |
| 3346 | list(0,-y,0,0,0,0))); |
| 3347 | for (j=1;j<=size(perms[i]);j++) |
| 3348 | { |
| 3349 | for (k=1;k<=size(perms[i][j]);k++) |
| 3350 | { |
| 3351 | D[k,3+j]=perms[i][j][k]; |
| 3352 | } |
| 3353 | } |
| 3354 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3355 | 1,1,1,1,1,1, |
| 3356 | 1,1,1,1,1,1, |
| 3357 | 1,1,1,1,1,1, |
| 3358 | 1,1,1,1,1,1, |
| 3359 | 1,1,1,1,1,1; |
| 3360 | def r3 = nc_algebra(C,D); |
| 3361 | setring(r3); |
| 3362 | expected = 0; |
| 3363 | obtained = checkIfProperNthShift(); |
| 3364 | if (expected !=obtained) |
| 3365 | { |
| 3366 | print("Test 4 for checkIfProperNthShift failed. Basering:"); |
| 3367 | basering; |
| 3368 | print("Expected:\n"); |
| 3369 | print(expected); |
| 3370 | print("obtained:\n"); |
| 3371 | print(obtained); |
| 3372 | result = 0; |
| 3373 | } |
| 3374 | kill r3; |
| 3375 | kill R3; |
| 3376 | } |
| 3377 | //Test 5: commutative ring |
| 3378 | ring R = 0,(n,s),lp; |
| 3379 | expected = 0; |
| 3380 | obtained = checkIfProperNthShift(); |
| 3381 | if (expected !=obtained) |
| 3382 | { |
| 3383 | print("Test 5 for checkIfProperNthShift failed. Basering:"); |
| 3384 | basering; |
| 3385 | print("Expected:\n"); |
| 3386 | print(expected); |
| 3387 | print("obtained:\n"); |
| 3388 | print(obtained); |
| 3389 | result = 0; |
| 3390 | } |
| 3391 | kill R; |
| 3392 | //Test 6: Proper 3rd shift algebra |
| 3393 | ring R = 0,(n1,n2,n3,s1,s2,s3),lp; |
| 3394 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3395 | 1,1,1,1,1,1, |
| 3396 | 1,1,1,1,1,1, |
| 3397 | 1,1,1,1,1,1, |
| 3398 | 1,1,1,1,1,1, |
| 3399 | 1,1,1,1,1,1; |
| 3400 | matrix D[6][6] = 0,0,0,s1,0,0, |
| 3401 | 0,0,0,0,s2,0, |
| 3402 | 0,0,0,0,0,s3; |
| 3403 | def r = nc_algebra(C,D); |
| 3404 | setring r; |
| 3405 | expected = 1; |
| 3406 | obtained = checkIfProperNthShift(); |
| 3407 | if (expected !=obtained) |
| 3408 | { |
| 3409 | print("Test 6 for checkIfProperNthShift failed. Basering:"); |
| 3410 | basering; |
| 3411 | print("Expected:\n"); |
| 3412 | print(expected); |
| 3413 | print("obtained:\n"); |
| 3414 | print(obtained); |
| 3415 | result = 0; |
| 3416 | } |
| 3417 | kill R; kill r; |
| 3418 | return(result); |
| 3419 | }//testing checkIfProperNthShift |
| 3420 | |
| 3421 | |
| 3422 | static proc checkIfProperNthWeyl() |
| 3423 | " |
| 3424 | INPUT: None |
| 3425 | OUTPUT: Checks whether the given basering is a proper Weyl algebra. |
| 3426 | Proper means in the sense of our algorithms, i.e. fulfilling |
| 3427 | the assumption that o ur basering is the Nth Weyl algebra and |
| 3428 | that the xs are the first n variables, the differential |
| 3429 | operators are the last n. Returns 1 if proper, 0 otherwise. |
| 3430 | " |
| 3431 | {//checkIfProperNthWeyl |
| 3432 | if (!ncfactor_isWeyl()) |
| 3433 | {return(0);} |
| 3434 | int i; |
| 3435 | for (i = 1; i<=nvars(basering) div 2; i++) |
| 3436 | { |
| 3437 | if (var(i + nvars(basering) div 2)*var(i) |
| 3438 | - var(i)*var(i+nvars(basering) div 2)!=1) |
| 3439 | { |
| 3440 | return(0); |
| 3441 | } |
| 3442 | } |
| 3443 | return(1); |
| 3444 | }//checkIfProperNthWeyl |
| 3445 | |
| 3446 | |
| 3447 | static proc test_checkIfProperNthWeyl() |
| 3448 | {//testing checkIfProperNthWeyl |
| 3449 | int result = 1; int i; int j; int k; |
| 3450 | //Test 1: proper 1st Weyl |
| 3451 | ring R = 0,(x,y),dp; |
| 3452 | def r= nc_algebra(1,1); |
| 3453 | setring r; |
| 3454 | int expected = 1; |
| 3455 | int obtained = checkIfProperNthWeyl(); |
| 3456 | if (expected !=obtained) |
| 3457 | { |
| 3458 | print("Test 1 for checkIfProperNthWeyl failed. Basering:"); |
| 3459 | basering; |
| 3460 | print("Expected:\n"); |
| 3461 | print(expected); |
| 3462 | print("obtained:\n"); |
| 3463 | print(obtained); |
| 3464 | result = 0; |
| 3465 | } |
| 3466 | kill R; kill r; |
| 3467 | //Test 2: non proper 1st Weyl |
| 3468 | ring R = 0,(x,y),dp; |
| 3469 | def r= nc_algebra(1,-1); |
| 3470 | setring r; |
| 3471 | expected = 0; |
| 3472 | obtained = checkIfProperNthWeyl(); |
| 3473 | if (expected !=obtained) |
| 3474 | { |
| 3475 | print("Test 2 for checkIfProperNthWeyl failed. Basering:"); |
| 3476 | basering; |
| 3477 | print("Expected:\n"); |
| 3478 | print(expected); |
| 3479 | print("obtained:\n"); |
| 3480 | print(obtained); |
| 3481 | result = 0; |
| 3482 | } |
| 3483 | kill R; kill r; |
| 3484 | //Test 3: All possible non-proper third Weyls |
| 3485 | list perms =list(list(list(1,0,0,0,0,0), |
| 3486 | list(0,0,1,0,0,0), |
| 3487 | list(0,1,0,0,0,0)), |
| 3488 | list(list(0,1,0,0,0,0), |
| 3489 | list(1,0,0,0,0,0), |
| 3490 | list(0,0,1,0,0,0)), |
| 3491 | list(list(0,1,0,0,0,0), |
| 3492 | list(0,0,1,0,0,0), |
| 3493 | list(1,0,0,0,0,0)), |
| 3494 | list(list(0,0,1,0,0,0), |
| 3495 | list(0,1,0,0,0,0), |
| 3496 | list(1,0,0,0,0,0)), |
| 3497 | list(list(0,0,1,0,0,0), |
| 3498 | list(1,0,0,0,0,0), |
| 3499 | list(0,1,0,0,0,0))); |
| 3500 | for(i=1;i<=size(perms);i++) |
| 3501 | { |
| 3502 | ring R3 = 0,(x,y,z,w,v,u),dp; |
| 3503 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3504 | 1,1,1,1,1,1, |
| 3505 | 1,1,1,1,1,1, |
| 3506 | 1,1,1,1,1,1, |
| 3507 | 1,1,1,1,1,1, |
| 3508 | 1,1,1,1,1,1; |
| 3509 | matrix D[6][6]; |
| 3510 | for (j=1;j<=size(perms[i]);j++) |
| 3511 | { |
| 3512 | for (k=1;k<=size(perms[i][j]);k++) |
| 3513 | { |
| 3514 | D[k,3+j]=perms[i][j][k]; |
| 3515 | } |
| 3516 | } |
| 3517 | def r3 = nc_algebra(C,D); |
| 3518 | setring(r3); |
| 3519 | expected = 0; |
| 3520 | obtained = checkIfProperNthWeyl(); |
| 3521 | if (expected !=obtained) |
| 3522 | { |
| 3523 | print("Test 3 for checkIfProperNthWeyl failed."); |
| 3524 | print("Expected:\n"); |
| 3525 | print(expected); |
| 3526 | print("obtained:\n"); |
| 3527 | print(obtained); |
| 3528 | result = 0; |
| 3529 | } |
| 3530 | kill r3; |
| 3531 | kill R3; |
| 3532 | } |
| 3533 | //Test 4: All reversed possibilities for the 3rd weyl algebra |
| 3534 | kill perms; |
| 3535 | list perms =list(list(list(-1,0,0,0,0,0), |
| 3536 | list(0,-1,0,0,0,0), |
| 3537 | list(0,0,-1,0,0,0)), |
| 3538 | list(list(-1,0,0,0,0,0), |
| 3539 | list(0,0,-1,0,0,0), |
| 3540 | list(0,-1,0,0,0,0)), |
| 3541 | list(list(0,-1,0,0,0,0), |
| 3542 | list(-1,0,0,0,0,0), |
| 3543 | list(0,0,-1,0,0,0)), |
| 3544 | list(list(0,-1,0,0,0,0), |
| 3545 | list(0,0,-1,0,0,0), |
| 3546 | list(-1,0,0,0,0,0)), |
| 3547 | list(list(0,0,-1,0,0,0), |
| 3548 | list(0,-1,0,0,0,0), |
| 3549 | list(-1,0,0,0,0,0)), |
| 3550 | list(list(0,0,-1,0,0,0), |
| 3551 | list(-1,0,0,0,0,0), |
| 3552 | list(0,-1,0,0,0,0))); |
| 3553 | for(i=1;i<=size(perms);i++) |
| 3554 | { |
| 3555 | ring R3 = 0,(x,y,z,w,v,u),dp; |
| 3556 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3557 | 1,1,1,1,1,1, |
| 3558 | 1,1,1,1,1,1, |
| 3559 | 1,1,1,1,1,1, |
| 3560 | 1,1,1,1,1,1, |
| 3561 | 1,1,1,1,1,1; |
| 3562 | matrix D[6][6]; |
| 3563 | for (j=1;j<=size(perms[i]);j++) |
| 3564 | { |
| 3565 | for (k=1;k<=size(perms[i][j]);k++) |
| 3566 | { |
| 3567 | D[k,3+j]=perms[i][j][k]; |
| 3568 | } |
| 3569 | } |
| 3570 | def r3 = nc_algebra(C,D); |
| 3571 | setring(r3); |
| 3572 | expected = 0; |
| 3573 | obtained = checkIfProperNthWeyl(); |
| 3574 | if (expected !=obtained) |
| 3575 | { |
| 3576 | print("Test 4 for checkIfProperNthWeyl failed."); |
| 3577 | print("Expected:\n"); |
| 3578 | print(expected); |
| 3579 | print("obtained:\n"); |
| 3580 | print(obtained); |
| 3581 | result = 0; |
| 3582 | } |
| 3583 | kill r3; |
| 3584 | kill R3; |
| 3585 | } |
| 3586 | //Test 5: Proper third Weyl algebra |
| 3587 | ring R = 0,(x1,x2,x3,d1,d2,d3),dp; |
| 3588 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3589 | 1,1,1,1,1,1, |
| 3590 | 1,1,1,1,1,1, |
| 3591 | 1,1,1,1,1,1, |
| 3592 | 1,1,1,1,1,1, |
| 3593 | 1,1,1,1,1,1; |
| 3594 | matrix D[6][6] = 0,0,0,1,0,0, |
| 3595 | 0,0,0,0,1,0, |
| 3596 | 0,0,0,0,0,1; |
| 3597 | def r= nc_algebra(C,D); |
| 3598 | setring r; |
| 3599 | expected = 1; |
| 3600 | obtained = checkIfProperNthWeyl(); |
| 3601 | if (expected !=obtained) |
| 3602 | { |
| 3603 | print("Test 5 for checkIfProperNthWeyl failed. Basering:"); |
| 3604 | basering; |
| 3605 | print("Expected:\n"); |
| 3606 | print(expected); |
| 3607 | print("obtained:\n"); |
| 3608 | print(obtained); |
| 3609 | result = 0; |
| 3610 | } |
| 3611 | kill R; kill r; |
| 3612 | //Test 6: Commutative ring |
| 3613 | ring R = 0,(x1,x2,x3,d1,d2,d3),dp; |
| 3614 | expected = 0; |
| 3615 | obtained = checkIfProperNthWeyl(); |
| 3616 | if (expected !=obtained) |
| 3617 | { |
| 3618 | print("Test 6 for checkIfProperNthWeyl failed. Basering:"); |
| 3619 | basering; |
| 3620 | print("Expected:\n"); |
| 3621 | print(expected); |
| 3622 | print("obtained:\n"); |
| 3623 | print(obtained); |
| 3624 | result = 0; |
| 3625 | } |
| 3626 | return(result); |
| 3627 | }//testing checkIfProperNthWeyl |
| 3628 | |
| 3629 | |
| 3630 | static proc checkIfProperNthQWeyl() |
| 3631 | " |
| 3632 | INPUT: None |
| 3633 | OUTPUT: Checks whether the given basering is a proper q-Weyl algebra. |
| 3634 | Proper means in the sense of our algorithms, i.e. fulfilling |
| 3635 | the assumption that o ur basering is the Nth Weyl algebra and |
| 3636 | that the xs are the first n variables, the differential |
| 3637 | operators are the last n. Returns 1 if proper, 0 otherwise. |
| 3638 | " |
| 3639 | {//checkIfProperNthQWeyl |
| 3640 | if (!ncfactor_isQWeyl()) |
| 3641 | {return(0);} |
| 3642 | int i; |
| 3643 | for (i = 1; i<=nvars(basering) div 2; i++) |
| 3644 | { |
| 3645 | if (var(i + nvars(basering) div 2)*var(i) |
| 3646 | - par(i)*var(i)*var(i+nvars(basering) div 2)!=1) |
| 3647 | { |
| 3648 | return(0); |
| 3649 | } |
| 3650 | } |
| 3651 | return(1); |
| 3652 | }//checkIfProperNthQWeyl |
| 3653 | |
| 3654 | |
| 3655 | static proc test_checkIfProperNthQWeyl() |
| 3656 | {//testing checkIfProperNthQWeyl |
| 3657 | int result = 1; |
| 3658 | int i; int j; int k; |
| 3659 | //Test 1: first Weyl algebra, x before d |
| 3660 | ring R = (0,q),(x,d),dp; |
| 3661 | def r = nc_algebra(q,1); |
| 3662 | setring(r); |
| 3663 | int expected = 1; |
| 3664 | int obtained = checkIfProperNthQWeyl(); |
| 3665 | if (expected !=obtained) |
| 3666 | { |
| 3667 | print("Test 1 for checkIfProperNthQWeyl failed."); |
| 3668 | print("Expected:\n"); |
| 3669 | print(expected); |
| 3670 | print("obtained:\n"); |
| 3671 | print(obtained); |
| 3672 | result = 0; |
| 3673 | } |
| 3674 | //Test 2: first Weyl algebra, d before x |
| 3675 | ring R2 = (0,q),(x,d),dp; |
| 3676 | def r2 = nc_algebra(q,-1); |
| 3677 | setring(r2); |
| 3678 | expected = 0; |
| 3679 | obtained = checkIfProperNthQWeyl(); |
| 3680 | if (expected !=obtained) |
| 3681 | { |
| 3682 | print("Test 2 for checkIfProperNthQWeyl failed."); |
| 3683 | print("Expected:\n"); |
| 3684 | print(expected); |
| 3685 | print("obtained:\n"); |
| 3686 | print(obtained); |
| 3687 | result = 0; |
| 3688 | } |
| 3689 | //Test 3: All possibilities for third Weyl algebra |
| 3690 | list perms =list(list(list(1,0,0,0,0,0), |
| 3691 | list(0,0,1,0,0,0), |
| 3692 | list(0,1,0,0,0,0)), |
| 3693 | list(list(0,1,0,0,0,0), |
| 3694 | list(1,0,0,0,0,0), |
| 3695 | list(0,0,1,0,0,0)), |
| 3696 | list(list(0,1,0,0,0,0), |
| 3697 | list(0,0,1,0,0,0), |
| 3698 | list(1,0,0,0,0,0)), |
| 3699 | list(list(0,0,1,0,0,0), |
| 3700 | list(0,1,0,0,0,0), |
| 3701 | list(1,0,0,0,0,0)), |
| 3702 | list(list(0,0,1,0,0,0), |
| 3703 | list(1,0,0,0,0,0), |
| 3704 | list(0,1,0,0,0,0))); |
| 3705 | for(i=1;i<=size(perms);i++) |
| 3706 | { |
| 3707 | ring R3 = (0,q(1..3)),(x,y,z,w,v,u),dp; |
| 3708 | matrix D[6][6]; |
| 3709 | for (j=1;j<=size(perms[i]);j++) |
| 3710 | { |
| 3711 | for (k=1;k<=size(perms[i][j]);k++) |
| 3712 | { |
| 3713 | D[k,3+j]=perms[i][j][k]; |
| 3714 | } |
| 3715 | } |
| 3716 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3717 | 1,1,1,1,1,1, |
| 3718 | 1,1,1,1,1,1, |
| 3719 | 1,1,1,1,1,1, |
| 3720 | 1,1,1,1,1,1, |
| 3721 | 1,1,1,1,1,1; |
| 3722 | for (j=1;j<=size(perms[i]);j++) |
| 3723 | { |
| 3724 | for (k=1;k<=size(perms[i][j]);k++) |
| 3725 | { |
| 3726 | if(perms[i][j][k]==1) |
| 3727 | { |
| 3728 | C[k,3+j]=q(j); |
| 3729 | } |
| 3730 | } |
| 3731 | } |
| 3732 | def r3 = nc_algebra(C,D); |
| 3733 | setring(r3); |
| 3734 | expected = 0; |
| 3735 | obtained = checkIfProperNthQWeyl(); |
| 3736 | if (expected !=obtained) |
| 3737 | { |
| 3738 | print("Test 3 for checkIfProperNthQWeyl failed. Basering:"); |
| 3739 | basering; |
| 3740 | print("Expected:\n"); |
| 3741 | print(expected); |
| 3742 | print("obtained:\n"); |
| 3743 | print(obtained); |
| 3744 | result = 0; |
| 3745 | } |
| 3746 | kill r3; |
| 3747 | kill R3; |
| 3748 | } |
| 3749 | //Test 4: All possibilities for third Weyl algebra reversed |
| 3750 | kill perms; |
| 3751 | list perms =list(list(list(-1,0,0,0,0,0), |
| 3752 | list(0,-1,0,0,0,0), |
| 3753 | list(0,0,-1,0,0,0)), |
| 3754 | list(list(-1,0,0,0,0,0), |
| 3755 | list(0,0,-1,0,0,0), |
| 3756 | list(0,-1,0,0,0,0)), |
| 3757 | list(list(0,-1,0,0,0,0), |
| 3758 | list(-1,0,0,0,0,0), |
| 3759 | list(0,0,-1,0,0,0)), |
| 3760 | list(list(0,-1,0,0,0,0), |
| 3761 | list(0,0,-1,0,0,0), |
| 3762 | list(-1,0,0,0,0,0)), |
| 3763 | list(list(0,0,-1,0,0,0), |
| 3764 | list(0,-1,0,0,0,0), |
| 3765 | list(-1,0,0,0,0,0)), |
| 3766 | list(list(0,0,-1,0,0,0), |
| 3767 | list(-1,0,0,0,0,0), |
| 3768 | list(0,-1,0,0,0,0))); |
| 3769 | for(i=1;i<=size(perms);i++) |
| 3770 | { |
| 3771 | ring R3 = (0,q(1..3)),(x,y,z,w,v,u),dp; |
| 3772 | matrix D[6][6]; |
| 3773 | matrix C[6][6] = 1,1,1,1,1,1, |
| 3774 | 1,1,1,1,1,1, |
| 3775 | 1,1,1,1,1,1, |
| 3776 | 1,1,1,1,1,1, |
| 3777 | 1,1,1,1,1,1, |
| 3778 | 1,1,1,1,1,1; |
| 3779 | for (j=1;j<=size(perms[i]);j++) |
| 3780 | { |
| 3781 | for (k=1;k<=size(perms[i][j]);k++) |
| 3782 | { |
| 3783 | if(perms[i][j][k]==-1) |
| 3784 | { |
| 3785 | C[k,3+j]=1/q(j); |
| 3786 | } |
| 3787 | } |
| 3788 | } |
| 3789 | for (j=1;j<=size(perms[i]);j++) |
| 3790 | { |
| 3791 | for (k=1;k<=size(perms[i][j]);k++) |
| 3792 | { |
| 3793 | D[k,3+j]=perms[i][j][k]; |
| 3794 | } |
| 3795 | } |
| 3796 | def r3 = nc_algebra(C,D); |
| 3797 | setring(r3); |
| 3798 | expected = 0; |
| 3799 | obtained = checkIfProperNthQWeyl(); |
| 3800 | if (expected !=obtained) |
| 3801 | { |
| 3802 | print("Test 4 for checkIfProperNthQWeyl failed. Basering:"); |
| 3803 | basering; |
| 3804 | print("Expected:\n"); |
| 3805 | print(expected); |
| 3806 | print("obtained:\n"); |
| 3807 | print(obtained); |
| 3808 | result = 0; |
| 3809 | } |
| 3810 | kill r3; |
| 3811 | kill R3; |
| 3812 | } |
| 3813 | //Test 5: SubQWeyl but not Weyl |
| 3814 | ring R4 = (0,q),(x,y,z),dp; |
| 3815 | matrix D[3][3] = 0,0,1,0,0,0,0,0,0; |
| 3816 | matrix C[3][3] = 1,1,q,1,1,1,1,1,1; |
| 3817 | def r4 = nc_algebra(C,D); |
| 3818 | expected = 0; |
| 3819 | obtained = checkIfProperNthQWeyl(); |
| 3820 | if (expected !=obtained) |
| 3821 | { |
| 3822 | print("Test 5 for checkIfProperNthQWeyl failed."); |
| 3823 | print("Expected:\n"); |
| 3824 | print(expected); |
| 3825 | print("obtained:\n"); |
| 3826 | print(obtained); |
| 3827 | result = 0; |
| 3828 | } |
| 3829 | //Test 6: Commutative ring |
| 3830 | ring R5 = 0,(x,d),dp; |
| 3831 | expected = 0; |
| 3832 | obtained = checkIfProperNthQWeyl(); |
| 3833 | if (expected !=obtained) |
| 3834 | { |
| 3835 | print("Test 6 for checkIfProperNthQWeyl failed."); |
| 3836 | print("Expected:\n"); |
| 3837 | print(expected); |
| 3838 | print("obtained:\n"); |
| 3839 | print(obtained); |
| 3840 | result = 0; |
| 3841 | } |
| 3842 | //Test 7: Weyl algebra |
| 3843 | ring R6 = 0,(x,d),dp; |
| 3844 | def r6 = nc_algebra(1,1); |
| 3845 | setring r6; |
| 3846 | expected = 0; |
| 3847 | obtained = checkIfProperNthQWeyl(); |
| 3848 | if (expected !=obtained) |
| 3849 | { |
| 3850 | print("Test 7 for checkIfProperNthQWeyl failed."); |
| 3851 | print("Expected:\n"); |
| 3852 | print(expected); |
| 3853 | print("obtained:\n"); |
| 3854 | print(obtained); |
| 3855 | result = 0; |
| 3856 | } |
| 3857 | //Test 8: q-Weyl, but with extra parameter |
| 3858 | ring R7 = (0,q,q2),(x,d),dp; |
| 3859 | def r7 = nc_algebra(q,1); |
| 3860 | setring r7; |
| 3861 | expected = 1; |
| 3862 | obtained = checkIfProperNthQWeyl(); |
| 3863 | if (expected !=obtained) |
| 3864 | { |
| 3865 | print("Test 8 for checkIfProperNthQWeyl failed."); |
| 3866 | print("Expected:\n"); |
| 3867 | print(expected); |
| 3868 | print("obtained:\n"); |
| 3869 | print(obtained); |
| 3870 | result = 0; |
| 3871 | } |
| 3872 | return(result); |
| 3873 | }//testing checkIfProperNthQWeyl |
| 3874 | |
| 3875 | |
| 3876 | ////////////////////////////////////////////////// |
| 3877 | //*****COMMUTATIVE FACTORIZATION HELPERS********** |
| 3878 | ////////////////////////////////////////////////// |
| 3879 | |
492 | | }//proc delete_dublicates_eval |
493 | | |
494 | | |
495 | | //==================================================* |
496 | | |
497 | | static proc combinekfinlf(list g, int nof) //nof stands for "number of factors" |
498 | | " |
499 | | given a list of factors g and a desired size nof, this |
500 | | procedure combines the factors, such that we recieve a |
501 | | list of the length nof. |
502 | | INPUT: A list of containing polynomials or any type where the *-operator is existent |
503 | | OUTPUT: All possibilities (without permutation of the given list) to combine the polynomials |
504 | | into nof polynomials given by the user. |
505 | | " |
506 | | {//Procedure combinekfinlf |
507 | | list result; |
508 | | int i; int j; int k; //iteration variables |
509 | | list fc; //fc stands for "factors combined" |
510 | | list temp; //a temporary store for factors |
511 | | def nofgl = size(g); //nofgl stands for "number of factors of the given list" |
512 | | if (nofgl == 0) |
513 | | {//g was the empty list |
514 | | return(result); |
515 | | }//g was the empty list |
516 | | if (nof <= 0) |
517 | | {//The user wants to recieve a negative number or no element as a result |
518 | | return(result); |
519 | | }//The user wants to recieve a negative number or no element as a result |
520 | | if (nofgl == nof) |
521 | | {//There are no factors to combine |
522 | | result = result + list(g); |
523 | | return(result); |
524 | | }//There are no factors to combine |
525 | | if (nof == 1) |
526 | | {//User wants to get just one factor |
527 | | result = result + list(list(product(g))); |
528 | | return(result); |
529 | | }//User wants to get just one factor |
530 | | for (i = nof; i > 1; i--) |
531 | | {//computing the possibilities that have at least one original factor from g |
532 | | for (j = i; j>=1; j--) |
533 | | {//shifting the window of combinable factors to the left |
534 | | //fc below stands for "factors combined" |
535 | | fc = combinekfinlf(list(g[(j)..(j+nofgl - i)]),nof - i + 1); |
536 | | for (k = 1; k<=size(fc); k++) |
537 | | {//iterating over the different solutions of the smaller problem |
538 | | if (j>1) |
539 | | {//There are g_i before the combination |
540 | | if (j+nofgl -i < nofgl) |
541 | | {//There are g_i after the combination |
542 | | temp = list(g[1..(j-1)]) + fc[k] + list(g[(j+nofgl-i+1)..nofgl]); |
543 | | }//There are g_i after the combination |
544 | | else |
545 | | {//There are no g_i after the combination |
546 | | temp = list(g[1..(j-1)]) + fc[k]; |
547 | | }//There are no g_i after the combination |
548 | | }//There are g_i before the combination |
549 | | if (j==1) |
550 | | {//There are no g_i before the combination |
551 | | if (j+ nofgl -i <nofgl) |
552 | | {//There are g_i after the combination |
553 | | temp = fc[k]+ list(g[(j + nofgl - i +1)..nofgl]); |
554 | | }//There are g_i after the combination |
555 | | }//There are no g_i before the combination |
556 | | result = result + list(temp); |
557 | | }//iterating over the different solutions of the smaller problem |
558 | | }//shifting the window of combinable factors to the left |
559 | | }//computing the possibilities that have at least one original factor from g |
560 | | for (i = 2; i<=nofgl div nof;i++) |
561 | | {//getting the other possible results |
562 | | result = result + combinekfinlf(list(product(list(g[1..i])))+list(g[(i+1)..nofgl]),nof); |
563 | | }//getting the other possible results |
564 | | result = delete_dublicates_noteval(result); |
565 | | return(result); |
566 | | }//Procedure combinekfinlf |
567 | | |
568 | | |
569 | | //==================================================* |
570 | | //merges two sets of factors ignoring common |
571 | | //factors |
572 | | static proc merge_icf(list l1, list l2, intvec limits) |
573 | | " |
574 | | DEPRECATED |
575 | | " |
576 | | {//proc merge_icf |
577 | | list g; |
578 | | list f; |
579 | | int i; int j; |
580 | | if (size(l1)==0) |
581 | | { |
582 | | return(list()); |
583 | | } |
584 | | if (size(l2)==0) |
585 | | { |
586 | | return(list()); |
587 | | } |
588 | | if (size(l2)<=size(l1)) |
589 | | {//l1 will be our g, l2 our f |
590 | | g = l1; |
591 | | f = l2; |
592 | | }//l1 will be our g, l2 our f |
593 | | else |
594 | | {//l1 will be our f, l2 our g |
595 | | g = l2; |
596 | | f = l1; |
597 | | }//l1 will be our f, l2 our g |
598 | | def result = combinekfinlf(g,size(f),limits); |
599 | | for (i = 1 ; i<= size(result); i++) |
600 | | {//Adding the factors of f to every possibility listed in temp |
601 | | for (j = 1; j<= size(f); j++) |
602 | | { |
603 | | result[i][j] = result[i][j]+f[j]; |
604 | | } |
605 | | if(!limitcheck(result[i],limits)) |
606 | | { |
607 | | result = delete(result,i); |
608 | | continue; |
609 | | } |
610 | | for (j = 1; j<=size(f);j++) |
611 | | {//Delete entry if there is a zero or an integer as a factor |
612 | | if (deg(result[i][j]) <= 0) |
613 | | {//found one |
614 | | result = delete(result,i); |
615 | | i--; |
616 | | break; |
617 | | }//found one |
618 | | }//Delete entry if there is a zero as factor |
619 | | }//Adding the factors of f to every possibility listed in temp |
620 | | return(result); |
621 | | }//proc merge_icf |
622 | | |
623 | | //==================================================* |
624 | | //merges two sets of factors with respect to the occurrence |
625 | | //of common factors |
626 | | static proc merge_cf(list l1, list l2, intvec limits) |
627 | | " |
628 | | DEPRECATED |
629 | | " |
630 | | {//proc merge_cf |
631 | | list g; |
632 | | list f; |
633 | | int i; int j; |
634 | | list pre; |
635 | | list post; |
636 | | list candidate; |
637 | | list temp; |
638 | | int temppos; |
639 | | if (size(l1)==0) |
640 | | {//the first list is empty |
641 | | return(list()); |
642 | | }//the first list is empty |
643 | | if(size(l2)==0) |
644 | | {//the second list is empty |
645 | | return(list()); |
646 | | }//the second list is empty |
647 | | if (size(l2)<=size(l1)) |
648 | | {//l1 will be our g, l2 our f |
649 | | g = l1; |
650 | | f = l2; |
651 | | }//l1 will be our g, l2 our f |
652 | | else |
653 | | {//l1 will be our f, l2 our g |
654 | | g = l2; |
655 | | f = l1; |
656 | | }//l1 will be our f, l2 our g |
657 | | list M; |
658 | | for (i = 2; i<size(f); i++) |
659 | | {//finding common factors of f and g... |
660 | | for (j=2; j<size(g);j++) |
661 | | {//... with g |
662 | | if (f[i] == g[j]) |
663 | | {//we have an equal pair |
664 | | M = M + list(list(i,j)); |
665 | | }//we have an equal pair |
666 | | }//... with g |
667 | | }//finding common factors of f and g... |
668 | | if (g[1]==f[1]) |
669 | | {//Checking for the first elements to be equal |
670 | | M = M + list(list(1,1)); |
671 | | }//Checking for the first elements to be equal |
672 | | if (g[size(g)]==f[size(f)]) |
673 | | {//Checking for the last elements to be equal |
674 | | M = M + list(list(size(f),size(g))); |
675 | | }//Checking for the last elements to be equal |
676 | | list result;//= list(list()); |
677 | | while(size(M)>0) |
678 | | {//set of equal pairs is not empty |
679 | | temp = M[1]; |
680 | | temppos = 1; |
681 | | for (i = 2; i<=size(M); i++) |
682 | | {//finding the minimal element of M |
683 | | if (M[i][1]<=temp[1]) |
684 | | {//a possible candidate that is smaller than temp could have been found |
685 | | if (M[i][1]==temp[1]) |
686 | | {//In this case we must look at the second number |
687 | | if (M[i][2]< temp[2]) |
688 | | {//the candidate is smaller |
689 | | temp = M[i]; |
690 | | temppos = i; |
691 | | }//the candidate is smaller |
692 | | }//In this case we must look at the second number |
693 | | else |
694 | | {//The candidate is definately smaller |
695 | | temp = M[i]; |
696 | | temppos = i; |
697 | | }//The candidate is definately smaller |
698 | | }//a possible candidate that is smaller than temp could have been found |
699 | | }//finding the minimal element of M |
700 | | M = delete(M, temppos); |
701 | | if(temp[1]>1) |
702 | | {//There are factors to combine before the equal factor |
703 | | if (temp[1]<size(f)) |
704 | | {//The most common case |
705 | | //first the combinations ignoring common factors |
706 | | pre = merge_icf(list(f[1..(temp[1]-1)]),list(g[1..(temp[2]-1)]),limits); |
707 | | post = merge_icf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits); |
708 | | for (i = 1; i <= size(pre); i++) |
709 | | {//all possible pre's... |
710 | | for (j = 1; j<= size(post); j++) |
711 | | {//...combined with all possible post's |
712 | | candidate = pre[i]+list(f[temp[1]])+post[j]; |
713 | | if (limitcheck(candidate,limits)) |
714 | | { |
715 | | result = result + list(candidate); |
716 | | } |
717 | | }//...combined with all possible post's |
718 | | }//all possible pre's... |
719 | | //Now the combinations with respect to common factors |
720 | | post = merge_cf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits); |
721 | | if (size(post)>0) |
722 | | {//There are factors to combine |
723 | | for (i = 1; i <= size(pre); i++) |
724 | | {//all possible pre's... |
725 | | for (j = 1; j<= size(post); j++) |
726 | | {//...combined with all possible post's |
727 | | candidate= pre[i]+list(f[temp[1]])+post[j]; |
728 | | if (limitcheck(candidate,limits)) |
729 | | { |
730 | | result = result + list(candidate); |
731 | | } |
732 | | }//...combined with all possible post's |
733 | | }//all possible pre's... |
734 | | }//There are factors to combine |
735 | | }//The most common case |
736 | | else |
737 | | {//the last factor is the common one |
738 | | pre = merge_icf(list(f[1..(temp[1]-1)]),list(g[1..(temp[2]-1)]),limits); |
739 | | for (i = 1; i<= size(pre); i++) |
740 | | {//iterating over the possible pre-factors |
741 | | candidate = pre[i]+list(f[temp[1]]); |
742 | | if (limitcheck(candidate,limits)) |
743 | | { |
744 | | result = result + list(candidate); |
745 | | } |
746 | | }//iterating over the possible pre-factors |
747 | | }//the last factor is the common one |
748 | | }//There are factors to combine before the equal factor |
749 | | else |
750 | | {//There are no factors to combine before the equal factor |
751 | | if (temp[1]<size(f)) |
752 | | {//Just a check for security |
753 | | //first without common factors |
754 | | post=merge_icf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits); |
755 | | for (i = 1; i<=size(post); i++) |
756 | | { |
757 | | candidate = list(f[temp[1]])+post[i]; |
758 | | if (limitcheck(candidate,limits)) |
759 | | { |
760 | | result = result + list(candidate); |
761 | | } |
762 | | } |
763 | | //Now with common factors |
764 | | post = merge_cf(list(f[(temp[1]+1)..size(f)]),list(g[(temp[2]+1..size(g))]),limits); |
765 | | if(size(post)>0) |
766 | | {//we could find other combinations |
767 | | for (i = 1; i<=size(post); i++) |
768 | | { |
769 | | candidate = list(f[temp[1]])+post[i]; |
770 | | if (limitcheck(candidate,limits)) |
771 | | { |
772 | | result = result + list(candidate); |
773 | | } |
774 | | } |
775 | | }//we could find other combinations |
776 | | }//Just a check for security |
777 | | }//There are no factors to combine before the equal factor |
778 | | }//set of equal pairs is not empty |
779 | | for (i = 1; i <= size(result); i++) |
780 | | {//delete those combinations, who have an entry with degree less or equal 0 |
781 | | for (j = 1; j<=size(result[i]);j++) |
782 | | {//Delete entry if there is a zero or an integer as a factor |
783 | | if (deg(result[i][j]) <= 0) |
784 | | {//found one |
785 | | result = delete(result,i); |
786 | | i--; |
787 | | break; |
788 | | }//found one |
789 | | }//Delete entry if there is a zero as factor |
790 | | }//delete those combinations, who have an entry with degree less or equal 0 |
791 | | return(result); |
792 | | }//proc merge_cf |
793 | | |
794 | | |
795 | | //==================================================* |
796 | | //merges two sets of factors |
797 | | |
798 | | static proc mergence(list l1, list l2, intvec limits) |
799 | | " |
800 | | DEPRECATED |
801 | | " |
802 | | {//Procedure mergence |
803 | | list g; |
804 | | list f; |
805 | | int k; int i; int j; |
806 | | list F = list(); |
807 | | list G = list(); |
808 | | list tempEntry; |
809 | | list comb; |
810 | | if (size(l2)<=size(l1)) |
811 | | {//l1 will be our g, l2 our f |
812 | | g = l1; |
813 | | f = l2; |
814 | | }//l1 will be our g, l2 our f |
815 | | else |
816 | | {//l1 will be our f, l2 our g |
817 | | g = l2; |
818 | | f = l1; |
819 | | }//l1 will be our f, l2 our g |
820 | | if (size(f)==1 or size(g)==1) |
821 | | {//One of them just has one entry |
822 | | if (size(f)== 1) {f = list(1) + f;} |
823 | | if (size(g) == 1) {g = list(1) + g;} |
824 | | }//One of them just has one entry |
825 | | //first, we need to add some latent -1's to the list f and to the list g in order |
826 | | //to get really all possibilities of combinations later |
827 | | for (i=1;i<=size(f)-1;i++) |
828 | | {//first iterator |
829 | | for (j=i+1;j<=size(f);j++) |
830 | | {//second iterator |
831 | | tempEntry = f; |
832 | | tempEntry[i] = (-1)*tempEntry[i]; |
833 | | tempEntry[j] = (-1)*tempEntry[j]; |
834 | | F = F + list(tempEntry); |
835 | | }//secont iterator |
836 | | }//first iterator |
837 | | F = F + list(f); |
838 | | //And now same game with g |
839 | | for (i=1;i<=size(g)-1;i++) |
840 | | {//first iterator |
841 | | for (j=i+1;j<=size(g);j++) |
842 | | {//second iterator |
843 | | tempEntry = g; |
844 | | tempEntry[i] = (-1)*tempEntry[i]; |
845 | | tempEntry[j] = (-1)*tempEntry[j]; |
846 | | G = G + list(tempEntry); |
847 | | }//secont iterator |
848 | | }//first iterator |
849 | | G = G + list(g); |
850 | | //Done with that |
851 | | |
852 | | list result; |
853 | | for (i = 1; i<=size(F); i++) |
854 | | {//Iterate over all entries in F |
855 | | for (j = 1;j<=size(G);j++) |
856 | | {//Same with G |
857 | | comb = combinekfinlf(F[i],2,limits); |
858 | | for (k = 1; k<= size(comb);k++) |
859 | | {//for all possibilities of combinations of the factors of f |
860 | | result = result + merge_cf(comb[k],G[j],limits); |
861 | | result = result + merge_icf(comb[k],G[j],limits); |
862 | | result = delete_dublicates_noteval(result); |
863 | | }//for all possibilities of combinations of the factors of f |
864 | | }//Same with G |
865 | | }//Iterate over all entries in F |
866 | | return(result); |
867 | | }//Procedure mergence |
868 | | |
869 | | |
870 | | //================================================== |
871 | | //Checks, whether a list of factors doesn't exceed the given limits |
872 | | static proc limitcheck(list g, intvec limits) |
873 | | " |
874 | | DEPRECATED |
875 | | " |
876 | | {//proc limitcheck |
877 | | int i; |
878 | | if (size(limits)!=3) |
879 | | {//check the input |
880 | | return(0); |
881 | | }//check the input |
882 | | if(size(g)==0) |
883 | | { |
884 | | return(0); |
885 | | } |
886 | | def prod = product(g); |
887 | | intvec iv11 = intvec(1,1); |
888 | | intvec iv10 = intvec(1,0); |
889 | | intvec iv01 = intvec(0,1); |
890 | | def limg = intvec(deg(prod,iv11) ,deg(prod,iv10),deg(prod,iv01)); |
891 | | for (i = 1; i<=size(limg);i++) |
892 | | {//the final check |
893 | | if(limg[i]>limits[i]) |
894 | | { |
895 | | return(0); |
896 | | } |
897 | | }//the final check |
898 | | return(1); |
899 | | }//proc limitcheck |
900 | | |
901 | | |
902 | | //==================================================* |
903 | | //one factorization of a homogeneous polynomial |
904 | | //in the first Weyl Algebra |
905 | | static proc homogfacFirstWeyl(poly h) |
906 | | "USAGE: homogfacFirstWeyl(h); h is a homogeneous polynomial in the |
907 | | first Weyl algebra with respect to the weight vector [-1,1] |
908 | | RETURN: list |
909 | | PURPOSE: Computes a factorization of a homogeneous polynomial h with |
910 | | respect to the weight vector [-1,1] in the first Weyl algebra |
911 | | THEORY: @code{homogfacFirstWeyl} returns a list with a factorization of the given, |
912 | | [-1,1]-homogeneous polynomial. If the degree of the polynomial is k with |
913 | | k positive, the last k entries in the output list are the second |
914 | | variable. If k is positive, the last k entries will be x. The other |
915 | | entries will be irreducible polynomials of degree zero or 1 resp. -1. |
916 | | SEE ALSO: homogfacFirstWeyl_all |
917 | | "{//proc homogfacFirstWeyl |
918 | | int p = printlevel-voice+2;//for dbprint |
919 | | def r = basering; |
920 | | poly hath; |
| 3980 | }//testing isInCommutativeSubRing |
| 3981 | |
| 3982 | |
| 3983 | static proc factor_commutative(poly h) |
| 3984 | "USAGE: factor_commutative(h); h is a polynomial in a |
| 3985 | non-commutative ring, for which all the variables that appear in a |
| 3986 | positive powers in the monomials of h are pairwise commutative. |
| 3987 | RETURN: list(list) |
| 3988 | PURPOSE: Sometimes, we end up having polynomials in a non-commutative |
| 3989 | ring, which lie in a commutative subring, and we can factor |
| 3990 | them in a commutative fashion. |
| 3991 | ASSUME: |
| 3992 | - k is a ring, such that factorize can factor any univariate and |
| 3993 | multivariate commutative polynomial over k. |
| 3994 | - h is in a commutative subring (NOT CHECKED) |
| 3995 | SEE ALSO: ncfactor |
| 3996 | "{//proc factor_commutative |
| 3997 | int p = printlevel-voice+2; |
925 | | intvec ivm11 = intvec(-1,1); |
926 | | if (!homogwithorder(h,ivm11)) |
927 | | {//The given polynomial is not homogeneous |
928 | | ERROR("Given polynomial was not [-1,1]-homogeneous"); |
| 4002 | if (deg(h)<=0) |
| 4003 | { |
| 4004 | dbprint(p,dbprintWhitespace + "h is a constant. Returning |
| 4005 | immediately"); |
| 4006 | return(list(list(h))); |
| 4007 | } |
| 4008 | def r = basering; |
| 4009 | list factorizeOutput; |
| 4010 | if (size(ringlist(basering))<=4) |
| 4011 | {//commutative ring case |
| 4012 | dbprint(p,dbprintWhitespace + "We are in a commutative |
| 4013 | ring. Factoring h using factorize."); |
| 4014 | factorizeOutput = factorize(h); |
| 4015 | }//commutative ring case |
| 4016 | else |
| 4017 | {//commutative subring case; |
| 4018 | dbprint(p,dbprintWhitespace + "We are in a commutative |
| 4019 | subring. Generating commutative ring.."); |
| 4020 | def rList = ringlist(basering); |
| 4021 | rList = delete(rList,5); |
| 4022 | rList = delete(rList,5); |
| 4023 | def tempRing = ring(rList); |
| 4024 | setring(tempRing); |
| 4025 | poly h = imap(r,h); |
| 4026 | dbprint(p, dbprintWhitespace+"Factoring h in commutative ring."); |
| 4027 | list tempResult = factorize(h); |
| 4028 | setring(r); |
| 4029 | factorizeOutput = imap(tempRing,tempResult); |
| 4030 | }//commutative subring case; |
| 4031 | dbprint(p,dbprintWhitespace + "Done commutatively factorizing. |
| 4032 | The result is:"); |
| 4033 | dbprint(p,factorizeOutput); |
| 4034 | dbprint(p,dbprintWhitespace+"Computing all permutations of this factorization."); |
| 4035 | list result = list(list()); |
| 4036 | for (i = 1; i<=size(factorizeOutput[1]); i++) |
| 4037 | { |
| 4038 | for (j = 1; j<=factorizeOutput[2][i]; j++) |
| 4039 | { |
| 4040 | result[1] = result[1] + list(factorizeOutput[1][i]); |
| 4041 | } |
| 4042 | } |
| 4043 | poly constantFactor = result[1][1]; |
| 4044 | result[1] = delete(result[1],1);//Deleting the constant factor |
| 4045 | result=permpp(result[1]); |
| 4046 | for (i = 1; i<=size(result);i++) |
| 4047 | {//Insert constant factor |
| 4048 | result[i] = insert(result[i],constantFactor); |
| 4049 | }//Insert constant factor |
| 4050 | dbprint(p,dbprintWhitespace+"Done."); |
| 4051 | result = delete_duplicates_noteval_and_sort(result); |
| 4052 | return(result); |
| 4053 | }//proc factor_commutative |
| 4054 | |
| 4055 | |
| 4056 | static proc test_factor_commutative() |
| 4057 | {//testing factor_commutative |
| 4058 | int result = 1; |
| 4059 | //Test 1: Commutative ring anyways |
| 4060 | ring R = 0,(x1,x2,d1,d2),dp; |
| 4061 | list expected = list(list(poly(1),x1+x2+d1+d2)); |
| 4062 | list obtained = factor_commutative(x1+x2+d1+d2); |
| 4063 | if (!isListEqual(expected,obtained)) |
| 4064 | { |
| 4065 | print("Test 1 for factor_commutative failed."); |
| 4066 | print("Expected:\n"); |
| 4067 | print(expected); |
| 4068 | print("obtained:\n"); |
| 4069 | print(obtained); |
| 4070 | result = 0; |
| 4071 | } |
| 4072 | kill R; |
| 4073 | //Test 2: Non-commutative ring, constant |
| 4074 | ring R = 0,(x,d),dp; |
| 4075 | def r = nc_algebra(1,1); |
| 4076 | setring(r); |
| 4077 | list expected = list(list(poly(3445))); |
| 4078 | list obtained = factor_commutative(3445); |
| 4079 | if (!isListEqual(expected,obtained)) |
| 4080 | { |
| 4081 | print("Test 2 for factor_commutative failed."); |
| 4082 | print("Expected:\n"); |
| 4083 | print(expected); |
| 4084 | print("obtained:\n"); |
| 4085 | print(obtained); |
| 4086 | result = 0; |
| 4087 | } |
| 4088 | kill r; kill R; |
| 4089 | //Test 3: Non-commutative ring, definitely commutative subring, irreducible |
| 4090 | ring R = 0,(x1,x2,d1,d2),dp; |
| 4091 | def r = Weyl(); |
| 4092 | setring r; |
| 4093 | list expected = list(list(poly(1), x1*d2+ x1 + d2 + 2)); |
| 4094 | list obtained = factor_commutative(x1*d2+ x1 + d2 + 2); |
| 4095 | if (!isListEqual(expected,obtained)) |
| 4096 | { |
| 4097 | print("Test 3 for factor_commutative failed."); |
| 4098 | print("Expected:\n"); |
| 4099 | print(expected); |
| 4100 | print("obtained:\n"); |
| 4101 | print(obtained); |
| 4102 | result = 0; |
| 4103 | } |
| 4104 | kill r; kill R; |
| 4105 | //Test 4: Non-commutative ring, definitely commutative subring, |
| 4106 | //reducible |
| 4107 | ring R = 0,(x1,x2,d1,d2),dp; |
| 4108 | def r = Weyl(); |
| 4109 | setring r; |
| 4110 | list expected = list(list(poly(1), x1*d2+ x1 + d2 + 2, x1*d2- x1 - |
| 4111 | d2 - 2), |
| 4112 | (list(poly(1), x1*d2- x1 - d2 - 2, x1*d2+ x1 + |
| 4113 | d2 + 2))); |
| 4114 | list obtained = factor_commutative((x1*d2+ x1 + d2 + 2)*(x1*d2- x1 - |
| 4115 | d2 - 2)); |
| 4116 | if (!isListEqual(expected,obtained)) |
| 4117 | { |
| 4118 | print("Test 4 for factor_commutative failed."); |
| 4119 | print("Expected:\n"); |
| 4120 | print(expected); |
| 4121 | print("obtained:\n"); |
| 4122 | print(obtained); |
| 4123 | result = 0; |
| 4124 | } |
| 4125 | kill r; kill R; |
| 4126 | return(result); |
| 4127 | }//testing factor_commutative |
| 4128 | |
| 4129 | |
| 4130 | static proc factorizeInt(number n) |
| 4131 | "Given an integer n, factorizeInt computes its factorization. The output is a list |
| 4132 | containing two lists. The first contains the prime factors, the second its powers. |
| 4133 | ASSUMPTIONS: |
| 4134 | - n is given as integer number |
| 4135 | "{//factorizeInt |
| 4136 | if (n==0) |
| 4137 | {return(list(list(0),list(1)));} |
| 4138 | int i; |
| 4139 | list temp = primefactors(n); |
| 4140 | if (n<0) |
| 4141 | {list result = list(list(-1),list(1));} |
| 4142 | else |
| 4143 | {list result = list(list(1),list(1));} |
| 4144 | result[1] = result[1] + temp[1]; |
| 4145 | result[2] = result[2] + temp[2]; |
| 4146 | return(result); |
| 4147 | }//factorizeInt |
| 4148 | |
| 4149 | |
| 4150 | static proc test_factorizeInt() |
| 4151 | {//Testing factorizeInt |
| 4152 | int result =1; |
| 4153 | //Test 1: factorizing 0 |
| 4154 | ring R = 0,(x),dp; |
| 4155 | list expected = list(list(0),list(1)); |
| 4156 | list obtained = factorizeInt(number(0)); |
| 4157 | if (!isListEqual(expected,obtained)) |
| 4158 | { |
| 4159 | print("Test 1 for factorizeInt failed."); |
| 4160 | print("Expected:\n"); |
| 4161 | print(expected); |
| 4162 | print("obtained:\n"); |
| 4163 | print(obtained); |
| 4164 | result = 0; |
| 4165 | } |
| 4166 | //Test 2: factorizing 1 |
| 4167 | expected = list(list(1),list(1)); |
| 4168 | obtained = factorizeInt(number(1)); |
| 4169 | if (!isListEqual(expected,obtained)) |
| 4170 | { |
| 4171 | print("Test 2 for factorizeInt failed."); |
| 4172 | print("Expected:\n"); |
| 4173 | print(expected); |
| 4174 | print("obtained:\n"); |
| 4175 | print(obtained); |
| 4176 | result = 0; |
| 4177 | } |
| 4178 | //Test 3: factorizing a positive composite |
| 4179 | expected = list(list(1,2,5),list(1,2,1)); |
| 4180 | obtained = factorizeInt(20); |
| 4181 | if (!isListEqual(expected,obtained)) |
| 4182 | { |
| 4183 | print("Test 3 for factorizeInt failed."); |
| 4184 | print("Expected:\n"); |
| 4185 | print(expected); |
| 4186 | print("obtained:\n"); |
| 4187 | print(obtained); |
| 4188 | result = 0; |
| 4189 | } |
| 4190 | //Test 4: factorizing a negative composite |
| 4191 | expected = list(list(-1,2,5),list(1,2,1)); |
| 4192 | obtained = factorizeInt(-20); |
| 4193 | if (!isListEqual(expected,obtained)) |
| 4194 | { |
| 4195 | print("Test 4 for factorizeInt failed."); |
| 4196 | print("Expected:\n"); |
| 4197 | print(expected); |
| 4198 | print("obtained:\n"); |
| 4199 | print(obtained); |
| 4200 | result = 0; |
| 4201 | } |
| 4202 | //Test 5: factoring a prime |
| 4203 | expected = list(list(1,23),list(1,1)); |
| 4204 | obtained = factorizeInt(23); |
| 4205 | if (!isListEqual(expected,obtained)) |
| 4206 | { |
| 4207 | print("Test 5 for factorizeInt failed."); |
| 4208 | print("Expected:\n"); |
| 4209 | print(expected); |
| 4210 | print("obtained:\n"); |
| 4211 | print(obtained); |
| 4212 | result = 0; |
| 4213 | } |
| 4214 | return(result); |
| 4215 | }//Testing factorizeInt |
| 4216 | |
| 4217 | |
| 4218 | static proc getAllCoeffTuplesComb(list l)" |
| 4219 | Given the output of factorizeInt ((a_1,...,a_n),(i_1,...,i_n)) , it returns all possible tuples |
| 4220 | of the set {(a,b) | There exists a real N!=emptyset subset of {1,...,n}, such that |
| 4221 | a = prod_{i \in N}a_i, b=prod_{i \not\in N} a_i} |
| 4222 | Assumption: The list is sorted from smallest integer to highest. |
| 4223 | - it is not the factorization of 0. |
| 4224 | " |
| 4225 | {//proc getAllCoeffTuplesComb |
| 4226 | list result; |
| 4227 | if (l[1][1] == 0) |
| 4228 | { |
| 4229 | ERROR("getAllCoeffTuplesComb: Zero Coefficients as leading and Tail Coeffs? |
| 4230 | That is not possible. Something went wrong."); |
| 4231 | } |
| 4232 | if (size(l[1]) == 1) |
| 4233 | {//Trivial Factorization, just 1 |
| 4234 | if (l[1][1] == 1) |
| 4235 | { |
| 4236 | return(list(list(number(1),number(1)),list(-number(1),-number(1)))); |
| 4237 | } |
| 4238 | else |
| 4239 | { |
| 4240 | return(list(list(-number(1),number(1)),list(number(1),-number(1)))); |
| 4241 | } |
| 4242 | }//Trivial Factorization, just 1 |
| 4243 | if (size(l[1]) == 2 and l[2][2]==1) |
| 4244 | {//Just a prime number |
| 4245 | if (l[1][1] == 1) |
| 4246 | { |
| 4247 | result = list(number(l[1][2]),number(1)),list(number(1),number(l[1][2])); |
| 4248 | result = result + list(list(number(-l[1][2]),number(-1)),list(number(-1),number(-l[1][2]))); |
| 4249 | return(result); |
| 4250 | } |
| 4251 | else |
| 4252 | { |
| 4253 | result = list(list(number(l[1][2]),number(-1)),list(number(1),number(-l[1][2]))); |
| 4254 | result = result + list(list(number(-l[1][2]),number(1)),list(number(-1),number(l[1][2]))); |
| 4255 | return(result); |
| 4256 | } |
| 4257 | }//Just a prime number |
| 4258 | //Now comes the interesting case: a product of primes |
| 4259 | list tempPrimeFactors; |
| 4260 | list tempPowersOfThem; |
| 4261 | int i; |
| 4262 | for (i = 2; i<=size(l[1]);i++) |
| 4263 | {//Removing the starting 1 or -1 to get the N's |
| 4264 | tempPrimeFactors[i-1] = l[1][i]; |
| 4265 | tempPowersOfThem[i-1] = l[2][i]; |
| 4266 | }//Removing the starting 1 or -1 to get the N's |
| 4267 | list Ns = getAllDivisorsFromFactList(list(tempPrimeFactors,tempPowersOfThem)); |
| 4268 | list tempTuples; |
| 4269 | number productOfl = multiplyFactIntOutput(l); |
| 4270 | if (productOfl<0){productOfl = -productOfl;} |
| 4271 | tempTuples = tempTuples + list(list(number(1),productOfl),list(productOfl,number(1))); |
| 4272 | for (i = 1; i<=size(Ns); i++) |
| 4273 | { |
| 4274 | if (productOfl/Ns[i]>Ns[i]) |
| 4275 | { |
| 4276 | tempTuples = tempTuples + list(list(Ns[i],productOfl/Ns[i]),list(productOfl/Ns[i],Ns[i])); |
| 4277 | } |
| 4278 | if (productOfl/Ns[i]==Ns[i]) |
| 4279 | { |
| 4280 | tempTuples = tempTuples + list(list(Ns[i],Ns[i])); |
| 4281 | } |
| 4282 | } |
| 4283 | //And now, it just remains to get the -1s and 1-s correctly to the tuples |
| 4284 | list tempEntry; |
| 4285 | if (l[1][1] == 1) |
| 4286 | { |
| 4287 | for (i = 1; i<=size(tempTuples);i++) |
| 4288 | {//Adding everything to result |
| 4289 | tempEntry = tempTuples[i]; |
| 4290 | result = result + list(tempEntry); |
| 4291 | result = result + list(list(-tempEntry[1], -tempEntry[2])); |
| 4292 | }//Adding everyThing to Result |
| 4293 | } |
| 4294 | else |
| 4295 | { |
| 4296 | for (i = 1; i<=size(tempTuples);i++) |
| 4297 | {//Adding everything to result |
| 4298 | tempEntry = tempTuples[i]; |
| 4299 | result = result + list(list(tempEntry[1],-tempEntry[2])); |
| 4300 | result = result + list(list(-tempEntry[1], tempEntry[2])); |
| 4301 | }//Adding everyThing to Result |
| 4302 | } |
| 4303 | return(delete_duplicates_noteval_and_sort(result)); |
| 4304 | }//proc getAllCoeffTuplesComb |
| 4305 | |
| 4306 | |
| 4307 | static proc test_getAllCoeffTuplesComb() |
| 4308 | {//testing getAllCoeffTuplesComb |
| 4309 | int result = 1; |
| 4310 | ring R = 0,(x),dp; |
| 4311 | //Test 1: 1 |
| 4312 | list input = factorizeInt(1); |
| 4313 | list expected = list(list(number(1),number(1)),list(-number(1),-number(1))); |
| 4314 | list obtained = getAllCoeffTuplesComb(input); |
| 4315 | if (!isListEqual(expected,obtained)) |
| 4316 | { |
| 4317 | print("Test 1 for getAllCoeffTuplesComb failed."); |
| 4318 | print("Expected:\n"); |
| 4319 | print(expected); |
| 4320 | print("obtained:\n"); |
| 4321 | print(obtained); |
| 4322 | result = 0; |
| 4323 | } |
| 4324 | //Test 2: prime |
| 4325 | input = factorizeInt(13); |
| 4326 | expected = sortFactorizations( |
| 4327 | list( |
| 4328 | list(number(1),number(13)),list(number(13),number(1)), |
| 4329 | list(-number(1),-number(13)),list(-number(13),-number(1)))); |
| 4330 | obtained = sortFactorizations(getAllCoeffTuplesComb(input)); |
| 4331 | if (!isListEqual(expected,obtained)) |
| 4332 | { |
| 4333 | print("Test 2 for getAllCoeffTuplesComb failed."); |
| 4334 | print("Expected:\n"); |
| 4335 | print(expected); |
| 4336 | print("obtained:\n"); |
| 4337 | print(obtained); |
| 4338 | result = 0; |
| 4339 | } |
| 4340 | //Test 3: composite |
| 4341 | input = factorizeInt(13*5); |
| 4342 | expected = sortFactorizations( |
| 4343 | list( |
| 4344 | list(number(1),number(13)*number(5)),list(number(13)*number(5),number(1)), |
| 4345 | list(number(13),number(5)),list(number(5),number(13)), |
| 4346 | list(-number(1),-number(13)*number(5)),list(-number(13)*number(5),-number(1)), |
| 4347 | list(-number(13),-number(5)),list(-number(5),-number(13)) |
| 4348 | )); |
| 4349 | obtained = sortFactorizations(getAllCoeffTuplesComb(input)); |
| 4350 | if (!isListEqual(expected,obtained)) |
| 4351 | { |
| 4352 | print("Test 3 for getAllCoeffTuplesComb failed."); |
| 4353 | print("Expected:\n"); |
| 4354 | print(expected); |
| 4355 | print("obtained:\n"); |
| 4356 | print(obtained); |
| 4357 | result = 0; |
| 4358 | } |
| 4359 | return(result); |
| 4360 | }//testing getAllCoeffTuplesComb |
| 4361 | |
| 4362 | |
| 4363 | ////////////////////////////////////////////////// |
| 4364 | //*FACTORIZATION RELATED GENERAL HELPER FUNCTIONS* |
| 4365 | ////////////////////////////////////////////////// |
| 4366 | |
| 4367 | |
| 4368 | static proc normalizeFactors(list factList) |
| 4369 | "INPUT: A list of factorizations, as outputted e.g. by facWeyl |
| 4370 | OUTPUT: If any entry in a factorization is not primitive, this function |
| 4371 | divides the common divisor out and multiplies the first entry with it. |
| 4372 | " |
| 4373 | {//normalizeFactors |
| 4374 | int i; int j; |
| 4375 | list result = factList; |
| 4376 | for (i = 1; i<=size(result); i++) |
| 4377 | {//iterating through every different factorization |
| 4378 | for (j=2; j<=size(result[i]); j++) |
| 4379 | {//Iterating through all respective factors |
| 4380 | if (content(result[i][j])!=number(1)) |
| 4381 | {//Got one where the content is not equal to 1 |
| 4382 | result[i][1] = result[i][1] * content(result[i][j]); |
| 4383 | result[i][j] = result[i][j] / content(result[i][j]); |
| 4384 | }//Got one where the content is not equal to 1 |
| 4385 | }//Iterating through all respective factors |
| 4386 | }//iterating through every different factorization |
| 4387 | return(result); |
| 4388 | }//normalizeFactors |
| 4389 | |
| 4390 | |
| 4391 | static proc test_normalizeFactors() |
| 4392 | {//testing normalizeFactors |
| 4393 | int result = 1; |
| 4394 | //Test 1: Empty list |
| 4395 | list expected = list(); |
| 4396 | list obtained = normalizeFactors(list()); |
| 4397 | if (!isListEqual(expected,obtained)) |
| 4398 | { |
| 4399 | print("Test 1 for normalizeFactors failed."); |
| 4400 | print("Expected:\n"); |
| 4401 | print(expected); |
| 4402 | print("obtained:\n"); |
| 4403 | print(obtained); |
| 4404 | result = 0; |
| 4405 | } |
| 4406 | //Test 2: list with only constant factor |
| 4407 | expected = list(list(2)); |
| 4408 | obtained = normalizeFactors(list(list(2))); |
| 4409 | if (!isListEqual(expected,obtained)) |
| 4410 | { |
| 4411 | print("Test 2 for normalizeFactors failed."); |
| 4412 | print("Expected:\n"); |
| 4413 | print(expected); |
| 4414 | print("obtained:\n"); |
| 4415 | print(obtained); |
| 4416 | result = 0; |
| 4417 | } |
| 4418 | // Test 3: list with one factor, content 1 |
| 4419 | ring R = 0,(x,y),dp; |
| 4420 | expected = list(list(2,x^2+y^2)); |
| 4421 | obtained = normalizeFactors(list(list(2,x^2+y^2))); |
| 4422 | if (!isListEqual(expected,obtained)) |
| 4423 | { |
| 4424 | print("Test 3 for normalizeFactors failed."); |
| 4425 | print("Expected:\n"); |
| 4426 | print(expected); |
| 4427 | print("obtained:\n"); |
| 4428 | print(obtained); |
| 4429 | result = 0; |
| 4430 | } |
| 4431 | kill R; |
| 4432 | // Test 4: list with one factor, content not 1 |
| 4433 | ring R = 0,(x,y),dp; |
| 4434 | list expected = list(list(number(6),x^2+y^2)); |
| 4435 | list obtained = normalizeFactors(list(list(2,3*x^2+3*y^2))); |
| 4436 | if (!isListEqual(expected,obtained)) |
| 4437 | { |
| 4438 | print("Test 4 for normalizeFactors failed."); |
| 4439 | print("Expected:\n"); |
| 4440 | print(expected); |
| 4441 | print("obtained:\n"); |
| 4442 | print(obtained); |
| 4443 | result = 0; |
| 4444 | } |
| 4445 | kill R; |
| 4446 | // Test 5: list with more than one factor, content 1 |
| 4447 | ring R = 0,(x,y),dp; |
| 4448 | list expected = list(list(2,x^2+y^2,x,y)); |
| 4449 | list obtained = normalizeFactors(list(list(2,x^2+y^2,x,y))); |
| 4450 | if (!isListEqual(expected,obtained)) |
| 4451 | { |
| 4452 | print("Test 5 for normalizeFactors failed."); |
| 4453 | print("Expected:\n"); |
| 4454 | print(expected); |
| 4455 | print("obtained:\n"); |
| 4456 | print(obtained); |
| 4457 | result = 0; |
| 4458 | } |
| 4459 | kill R; |
| 4460 | //Test 6: list with more than one factor, content not 1 |
| 4461 | ring R = 0,(x,y),dp; |
| 4462 | list expected = list(list(number(12),x^2+y^2,x,y)); |
| 4463 | list obtained = normalizeFactors(list(list(2,x^2+y^2,2*x,3*y))); |
| 4464 | if (!isListEqual(expected,obtained)) |
| 4465 | { |
| 4466 | print("Test 6 for normalizeFactors failed."); |
| 4467 | print("Expected:\n"); |
| 4468 | print(expected); |
| 4469 | print("obtained:\n"); |
| 4470 | print(obtained); |
| 4471 | result = 0; |
| 4472 | } |
| 4473 | return(result); |
| 4474 | }//testing normalizeFactors |
| 4475 | |
| 4476 | |
| 4477 | static proc divides(poly p1, poly p2,map invo, list #) |
| 4478 | "Tests, whether p1 divides p2 either from left or from right. The involution invo is needed |
| 4479 | for checking both sides. The optional argument is needed in order to also return the other factor. |
| 4480 | RETURN: If no optional argument is given, it will just return 1 or 0. |
| 4481 | Otherwise a list with at least one element |
| 4482 | Case 1: p1 does not divide p2 from any side. Then the output will be the empty list. |
| 4483 | Case 2: p2 does divide p2 from one side at least. |
| 4484 | Then it returns a list with tuples p,q, such that p or q equals p1 and |
| 4485 | pq = p2. |
| 4486 | ASSUMPTIONS: - The map invo is an involution on the basering." |
| 4487 | {//proc divides |
| 4488 | list result = list(); |
| 4489 | poly tempfactor; |
| 4490 | if (involution(reduce(involution(p2,invo),std(involution(ideal(p1),invo))),invo)==0) |
| 4491 | {//p1 is a left divisor |
| 4492 | if(size(#)==0){return(1);} |
| 4493 | tempfactor = involution(lift(involution(p1,invo),involution(p2,invo))[1,1],invo); |
| 4494 | result = result + list(list(content(p1)*content(p2), |
| 4495 | p1/content(p1),tempfactor/content(tempfactor))); |
| 4496 | }//p1 is a left divisor |
| 4497 | |
| 4498 | if (reduce(p2,std(ideal(p1))) == 0) |
| 4499 | {//p1 is a right divisor |
| 4500 | if(size(#)==0){return(1);} |
| 4501 | tempfactor = lift(p1, p2)[1,1]; |
| 4502 | result = result + list(list(content(p1)*content(p2), |
| 4503 | tempfactor/content(tempfactor),p1/content(p1))); |
| 4504 | }//p1 is already a right divisor |
| 4505 | if (size(#)==0){return(0);} |
| 4506 | return(result); |
| 4507 | }//proc divides |
| 4508 | |
| 4509 | |
| 4510 | static proc test_divides() |
| 4511 | {//testing divides |
| 4512 | int result = 1; |
| 4513 | //Test 1: both polys are constant |
| 4514 | ring R = 0,(x,y),dp; |
| 4515 | def r = nc_algebra(1,1); |
| 4516 | setring r; |
| 4517 | map invo = r, -x , y; |
| 4518 | int expected = 1; |
| 4519 | int obtained = divides(1,2,invo); |
| 4520 | if (expected!=obtained) |
| 4521 | { |
| 4522 | print("Test 1 for divides failed."); |
| 4523 | print("Expected:\n"); |
| 4524 | print(expected); |
| 4525 | print("obtained:\n"); |
| 4526 | print(obtained); |
| 4527 | result = 0; |
| 4528 | } |
| 4529 | //Test 2: poly 1 does not divide poly 2 |
| 4530 | expected = 0; |
| 4531 | obtained = divides(x+y, x-y, invo); |
| 4532 | if (expected!=obtained) |
| 4533 | { |
| 4534 | print("Test 2 for divides failed."); |
| 4535 | print("Expected:\n"); |
| 4536 | print(expected); |
| 4537 | print("obtained:\n"); |
| 4538 | print(obtained); |
| 4539 | result = 0; |
| 4540 | } |
| 4541 | //Test 3: poly 1 does divide poly 2 from the left |
| 4542 | expected = 1; |
| 4543 | obtained = divides(x+y, (x+y)*(x-y), invo); |
| 4544 | list poly_expected = list(list(number(1),x+y,x-y)); |
| 4545 | list poly_obtained = divides(x+y, (x+y)*(x-y), invo,1); |
| 4546 | if (expected!=obtained||!isListEqual(poly_expected,poly_obtained)) |
| 4547 | { |
| 4548 | print("Test 3 for divides failed."); |
| 4549 | print("Expected 1:\n"); |
| 4550 | print(expected); |
| 4551 | print("Obtained 1:\n"); |
| 4552 | print(obtained); |
| 4553 | print("Expected 2:\n"); |
| 4554 | print(poly_expected); |
| 4555 | print("Obtained 2:\n"); |
| 4556 | print(poly_obtained); |
| 4557 | result = 0; |
| 4558 | } |
| 4559 | //Test 4: poly 1 does divide poly 2 from the right |
| 4560 | expected = 1; |
| 4561 | obtained = divides(x+y, (x-y)*(x+y), invo); |
| 4562 | poly_expected = list(list(1,x-y,x+y)); |
| 4563 | poly_obtained = divides(x+y, (x-y)*(x+y), invo,1); |
| 4564 | if (expected!=obtained) |
| 4565 | { |
| 4566 | print("Test 4 for divides failed."); |
| 4567 | print("Expected:\n"); |
| 4568 | print(expected); |
| 4569 | print("obtained:\n"); |
| 4570 | print(obtained); |
| 4571 | print("Expected 2:\n"); |
| 4572 | print(poly_expected); |
| 4573 | print("Obtained 2:\n"); |
| 4574 | print(poly_obtained); |
| 4575 | result = 0; |
| 4576 | } |
| 4577 | kill R; kill r; |
| 4578 | //Test 5: different algebra, no division |
| 4579 | ring R = 0,(x1,x2,n1,n2),dp; |
| 4580 | matrix C[4][4] = 1,1,1,1, |
| 4581 | 1,1,1,1, |
| 4582 | 1,1,1,1, |
| 4583 | 1,1,1,1; |
| 4584 | matrix D[4][4] = 0,0,n1,0, |
| 4585 | 0,0,0,n2, |
| 4586 | 0,0,0,0, |
| 4587 | 0,0,0,0; |
| 4588 | def r = nc_algebra(C,D); |
| 4589 | setring r; |
| 4590 | map invo = r, -x1,-x2,n1,n2; |
| 4591 | expected = 0; |
| 4592 | obtained = divides(x1+n1, (x1-n1), invo); |
| 4593 | if (expected!=obtained) |
| 4594 | { |
| 4595 | print("Test 5 for divides failed."); |
| 4596 | print("Expected:\n"); |
| 4597 | print(expected); |
| 4598 | print("obtained:\n"); |
| 4599 | print(obtained); |
| 4600 | result = 0; |
| 4601 | } |
| 4602 | //Test 6: different algebra, division from both sides |
| 4603 | expected = 1; |
| 4604 | obtained = divides(x1+n1, (x1+n1)*(x1-n1)*(x1+n1), invo); |
| 4605 | list poly_expected = list(list(number(1), (x1+n1),(x1-n1)*(x1+n1)), |
| 4606 | list(number(1), (x1+n1)*(x1-n1),(x1+n1))); |
| 4607 | list poly_obtained = divides(x1+n1, (x1+n1)*(x1-n1)*(x1+n1), invo,1); |
| 4608 | if (expected!=obtained||!isListEqual(poly_expected,poly_obtained)) |
| 4609 | { |
| 4610 | print("Test 6 for divides failed."); |
| 4611 | print("Expected:\n"); |
| 4612 | print(expected); |
| 4613 | print("obtained:\n"); |
| 4614 | print(obtained); |
| 4615 | print("Expected 2:\n"); |
| 4616 | print(poly_expected); |
| 4617 | print("Obtained 2:\n"); |
| 4618 | print(poly_obtained); |
| 4619 | result = 0; |
| 4620 | } |
| 4621 | //Test 7: Content is not 1 |
| 4622 | expected = 1; |
| 4623 | obtained = divides(x1+n1, 5*(x1+n1)*(x1-n1)*(x1+n1), invo); |
| 4624 | poly_expected = list(list(number(5), (x1+n1),(x1-n1)*(x1+n1)), |
| 4625 | list(number(5), (x1+n1)*(x1-n1),(x1+n1))); |
| 4626 | poly_obtained = divides(x1+n1, 5*(x1+n1)*(x1-n1)*(x1+n1), invo,1); |
| 4627 | if (expected!=obtained||!isListEqual(poly_expected,poly_obtained)) |
| 4628 | { |
| 4629 | print("Test 7 for divides failed."); |
| 4630 | print("Expected:\n"); |
| 4631 | print(expected); |
| 4632 | print("obtained:\n"); |
| 4633 | print(obtained); |
| 4634 | print("Expected 2:\n"); |
| 4635 | print(poly_expected); |
| 4636 | print("Obtained 2:\n"); |
| 4637 | print(poly_obtained); |
| 4638 | result = 0; |
| 4639 | } |
| 4640 | return(result); |
| 4641 | }//testing divides |
| 4642 | |
| 4643 | |
| 4644 | static proc multiplyFactIntOutput(list l) |
| 4645 | "Given the output of factorizeInt, this method computes the product of it." |
| 4646 | {//proc multiplyFactIntOutput |
| 4647 | int i; |
| 4648 | number result = 1; |
| 4649 | for (i = 1; i<=size(l[1]); i++) |
| 4650 | { |
| 4651 | result = result*(l[1][i])^(l[2][i]); |
| 4652 | } |
| 4653 | return(result); |
| 4654 | }//proc multiplyFactIntOutput |
| 4655 | |
| 4656 | |
| 4657 | static proc test_multiplyFactIntOutput() |
| 4658 | {//testing multiplyFactIntOutput |
| 4659 | int result = 1; |
| 4660 | //Test 1: empty list |
| 4661 | ring R = 0,(x),dp; |
| 4662 | number expected = 1; |
| 4663 | number obtained = multiplyFactIntOutput(list(list(),list())); |
| 4664 | if (expected!=obtained) |
| 4665 | { |
| 4666 | print("Test 1 for multiplyFactIntOutput failed."); |
| 4667 | print("Expected:\n"); |
| 4668 | print(expected); |
| 4669 | print("obtained:\n"); |
| 4670 | print(obtained); |
| 4671 | result = 0; |
| 4672 | } |
| 4673 | //Test 2: 1 |
| 4674 | expected = 1; |
| 4675 | obtained = multiplyFactIntOutput(factorizeInt(1)); |
| 4676 | if (expected!=obtained) |
| 4677 | { |
| 4678 | print("Test 2 for multiplyFactIntOutput failed."); |
| 4679 | print("Expected:\n"); |
| 4680 | print(expected); |
| 4681 | print("obtained:\n"); |
| 4682 | print(obtained); |
| 4683 | result = 0; |
| 4684 | } |
| 4685 | //Test 3: prime |
| 4686 | expected = 5; |
| 4687 | obtained = multiplyFactIntOutput(factorizeInt(5)); |
| 4688 | if (expected!=obtained) |
| 4689 | { |
| 4690 | print("Test 3 for multiplyFactIntOutput failed."); |
| 4691 | print("Expected:\n"); |
| 4692 | print(expected); |
| 4693 | print("obtained:\n"); |
| 4694 | print(obtained); |
| 4695 | result = 0; |
| 4696 | } |
| 4697 | //Test 4: Arbitrary composite |
| 4698 | expected = 5*10*66; |
| 4699 | obtained = multiplyFactIntOutput(factorizeInt(5*10*66)); |
| 4700 | if (expected!=obtained) |
| 4701 | { |
| 4702 | print("Test 4 for multiplyFactIntOutput failed."); |
| 4703 | print("Expected:\n"); |
| 4704 | print(expected); |
| 4705 | print("obtained:\n"); |
| 4706 | print(obtained); |
| 4707 | result = 0; |
| 4708 | } |
| 4709 | //Test 5: 0 |
| 4710 | expected = 0; |
| 4711 | obtained = multiplyFactIntOutput(factorizeInt(0)); |
| 4712 | if (expected!=obtained) |
| 4713 | { |
| 4714 | print("Test 5 for multiplyFactIntOutput failed."); |
| 4715 | print("Expected:\n"); |
| 4716 | print(expected); |
| 4717 | print("obtained:\n"); |
| 4718 | print(obtained); |
| 4719 | result = 0; |
| 4720 | } |
| 4721 | return(result); |
| 4722 | }//testing multiplyFactIntOutput |
| 4723 | |
| 4724 | |
| 4725 | //Testfac: Given a list with different factorizations of |
| 4726 | // one polynomial, the following procedure checks |
| 4727 | // whether they all refer to the same polynomial. |
| 4728 | // If they do, the output will be a list, that contains |
| 4729 | // the product of each factorization. If not, the empty |
| 4730 | // list will be returned. |
| 4731 | // If the optional argument # is given (i.e. the polynomial |
| 4732 | // which is factorized by the elements of the given list), |
| 4733 | // then we look, if the entries are factorizations of p |
| 4734 | // and if not, a list with the products subtracted by p |
| 4735 | // will be returned |
| 4736 | proc testNCfac(list l, list #) |
| 4737 | "USAGE: testNCfac(l[,p,b]); l is a list, p is an optional poly, b is 1 or 0 |
| 4738 | RETURN: Case 1: No optional argument. In this case the output is 1, if the |
| 4739 | entries in the given list represent the same polynomial or 0 |
| 4740 | otherwise. |
| 4741 | Case 2: One optional argument p is given. In this case it returns 1, |
| 4742 | if all the entries in l are factorizations of p, otherwise 0. |
| 4743 | Case 3: Second optional b is given. In this case a list is returned |
| 4744 | containing the difference between the product of each entry in |
| 4745 | l and p. |
| 4746 | ASSUME: basering is the first Weyl algebra, the entries of l are polynomials |
| 4747 | PURPOSE: Checks whether a list of factorizations contains factorizations of |
| 4748 | the same element in the first Weyl algebra |
| 4749 | THEORY: @code{testNCfac} multiplies out each factorization and checks whether |
| 4750 | each factorization was a factorization of the same element. |
| 4751 | @* - if there is only a list given, the output will be 0, if it |
| 4752 | does not contain factorizations of the same element. Otherwise the output |
| 4753 | will be 1. |
| 4754 | @* - if there is a polynomial in the second argument, then the procedure checks |
| 4755 | whether the given list contains factorizations of this polynomial. If it |
| 4756 | does, then the output depends on the third argument. If it is not given, |
| 4757 | the procedure will check whether the factorizations in the list |
| 4758 | l are associated to this polynomial and return either 1 or 0, respectively. |
| 4759 | If the third argument is given, the output will be a list with |
| 4760 | the length of the given one and in each entry is the product of one |
| 4761 | entry in l subtracted by the polynomial. |
| 4762 | EXAMPLE: example testNCfac; shows examples |
| 4763 | SEE ALSO: facFirstWeyl, facSubWeyl, facFirstShift |
| 4764 | "{//proc testfac |
| 4765 | int p = printlevel - voice + 2; |
| 4766 | int i; |
| 4767 | string dbprintWhitespace = ""; |
| 4768 | for (i = 1; i<=voice;i++) |
| 4769 | {dbprintWhitespace = dbprintWhitespace + " ";} |
| 4770 | dbprint(p,dbprintWhitespace + " Checking the input"); |
| 4771 | if (size(l)==0) |
| 4772 | {//The empty list is given |
| 4773 | dbprint(p,dbprintWhitespace + " Given list was empty"); |
947 | | }//There are more x than y |
| 4798 | result = insert(result, product(l[i])); |
| 4799 | }//iterate over the elements of the given list |
| 4800 | return(valid); |
| 4801 | }//No optional argument is given |
| 4802 | else |
| 4803 | { |
| 4804 | dbprint(p,dbprintWhitespace + " Optional arguments are given."); |
| 4805 | int valid = 1; |
| 4806 | for (i = size(l);i>=1;i--) |
| 4807 | {//iterate over the elements of the given list |
| 4808 | if (product(l[i])!=#[1]) |
| 4809 | { |
| 4810 | valid = 0; |
| 4811 | } |
| 4812 | result = insert(result, product(l[i])-#[1]); |
| 4813 | }//iterate over the elements of the given list |
| 4814 | if(size(#)==2) |
| 4815 | { |
| 4816 | dbprint(p,dbprintWhitespace + " A third argument is given. Output is a list now."); |
| 4817 | return(result); |
| 4818 | } |
| 4819 | return(valid); |
| 4820 | } |
| 4821 | }//proc testfac |
| 4822 | example |
| 4823 | { |
| 4824 | "EXAMPLE:";echo=2; |
| 4825 | ring r = 0,(x,y),dp; |
| 4826 | def R = nc_algebra(1,1); |
| 4827 | setring R; |
| 4828 | poly h = (x^2*y^2+1)*(x^2); |
| 4829 | def t1 = facFirstWeyl(h); |
| 4830 | //fist a correct list |
| 4831 | testNCfac(t1); |
| 4832 | //now a correct list with the factorized polynomial |
| 4833 | testNCfac(t1,h); |
| 4834 | //now we put in an incorrect list without a polynomial |
| 4835 | t1[3][3] = y; |
| 4836 | testNCfac(t1); |
| 4837 | // take h as additional input |
| 4838 | testNCfac(t1,h); |
| 4839 | // take h as additional input and output list of differences |
| 4840 | testNCfac(t1,h,1); |
| 4841 | } |
| 4842 | |
| 4843 | |
| 4844 | static proc test_testNCfac() |
| 4845 | {//testing testNCfac |
| 4846 | int result = 1; |
| 4847 | //Test 1: 1, no second or third parameter |
| 4848 | int expected = 1; |
| 4849 | int obtained = testNCfac(list(list(1))); |
| 4850 | if (expected!=obtained) |
| 4851 | { |
| 4852 | print("Test 1 for testNCfac failed."); |
| 4853 | print("Expected:\n"); |
| 4854 | print(expected); |
| 4855 | print("obtained:\n"); |
| 4856 | print(obtained); |
| 4857 | result = 0; |
| 4858 | } |
| 4859 | //Test 2: 1, second parameter, no third parameter |
| 4860 | expected = 1; |
| 4861 | obtained = testNCfac(list(list(1)),1); |
| 4862 | if (expected!=obtained) |
| 4863 | { |
| 4864 | print("Test 2 for testNCfac failed."); |
| 4865 | print("Expected:\n"); |
| 4866 | print(expected); |
| 4867 | print("obtained:\n"); |
| 4868 | print(obtained); |
| 4869 | result = 0; |
| 4870 | } |
| 4871 | //Test 3: 1, all possible parameters set |
| 4872 | list expected_third = list(0); |
| 4873 | list obtained_third = testNCfac(list(list(1)),1,1); |
| 4874 | if (!isListEqual(expected_third,obtained_third)) |
| 4875 | { |
| 4876 | print("Test 3 for testNCfac failed."); |
| 4877 | print("Expected:\n"); |
| 4878 | print(expected_third); |
| 4879 | print("obtained:\n"); |
| 4880 | print(obtained_third); |
| 4881 | result = 0; |
| 4882 | } |
| 4883 | //Test 4: correct factorization, more than one element, no second or |
| 4884 | //third parameter |
| 4885 | ring R = 0,(x,d),dp; |
| 4886 | def r = nc_algebra(1,1); |
| 4887 | setring r; |
| 4888 | expected = 1; |
| 4889 | obtained = |
| 4890 | testNCfac(list(list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1), |
| 4891 | list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4))); |
| 4892 | if (expected!=obtained) |
| 4893 | { |
| 4894 | print("Test 4 for testNCfac failed."); |
| 4895 | print("Expected:\n"); |
| 4896 | print(expected); |
| 4897 | print("obtained:\n"); |
| 4898 | print(obtained); |
| 4899 | result = 0; |
| 4900 | } |
| 4901 | //Test 5: correct factorization, more than one element, correct second |
| 4902 | //but not third parameter |
| 4903 | expected = 1; |
| 4904 | obtained = |
| 4905 | testNCfac(list(list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1), |
| 4906 | list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4)), |
| 4907 | (x^6+2*x^4-3*x^2)*d^2-(4*x^5-4*x^4-12*x^2-12*x)*d + |
| 4908 | (6*x^4-12*x^3-6*x^2-24*x-12)); |
| 4909 | if (expected!=obtained) |
| 4910 | { |
| 4911 | print("Test 5 for testNCfac failed."); |
| 4912 | print("Expected:\n"); |
| 4913 | print(expected); |
| 4914 | print("obtained:\n"); |
| 4915 | print(obtained); |
| 4916 | result = 0; |
| 4917 | } |
| 4918 | //Test 6: incorrect factorization, more than one element, incorrect second |
| 4919 | //but not third parameter |
| 4920 | expected = 0; |
| 4921 | obtained = |
| 4922 | testNCfac(list(list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1), |
| 4923 | list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4)), |
| 4924 | (x^6+2*x^4-3*x^2)*d^2-(4*x^5-4*x^4-12*x^2-12*x)*d + |
| 4925 | (6*x^4-12*x^3-6*x^2-24*x+12)); |
| 4926 | if (expected!=obtained) |
| 4927 | { |
| 4928 | print("Test 6 for testNCfac failed."); |
| 4929 | print("Expected:\n"); |
| 4930 | print(expected); |
| 4931 | print("obtained:\n"); |
| 4932 | print(obtained); |
| 4933 | result = 0; |
| 4934 | } |
| 4935 | //Test 7: incorrect factorization, more than one element, no second |
| 4936 | //or third parameter |
| 4937 | expected = 0; |
| 4938 | obtained = |
| 4939 | testNCfac(list(list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1), |
| 4940 | list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x-4))); |
| 4941 | if (expected!=obtained) |
| 4942 | { |
| 4943 | print("Test 7 for testNCfac failed."); |
| 4944 | print("Expected:\n"); |
| 4945 | print(expected); |
| 4946 | print("obtained:\n"); |
| 4947 | print(obtained); |
| 4948 | result = 0; |
| 4949 | } |
| 4950 | //Test 8: correct factorization, more than one element, correct second |
| 4951 | //and third parameter |
| 4952 | expected_third = list(poly(0),poly(0)); |
| 4953 | obtained_third = |
| 4954 | testNCfac(list(list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1), |
| 4955 | list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4)), |
| 4956 | (x^6+2*x^4-3*x^2)*d^2-(4*x^5-4*x^4-12*x^2-12*x)*d + |
| 4957 | (6*x^4-12*x^3-6*x^2-24*x-12),1); |
| 4958 | if (!isListEqual(expected_third,obtained_third)) |
| 4959 | { |
| 4960 | print("Test 8 for testNCfac failed."); |
| 4961 | print("Expected:\n"); |
| 4962 | print(expected_third); |
| 4963 | print("obtained:\n"); |
| 4964 | print(obtained_third); |
| 4965 | result = 0; |
| 4966 | } |
| 4967 | //Test 9: incorrect factorization, more than one element, correct second |
| 4968 | //and third parameter |
| 4969 | expected_third = list(poly(2x4d-2x3d-6x3+6x2d+12x2-6xd-6x+24),poly(0)); |
| 4970 | obtained_third = |
| 4971 | testNCfac(list(list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x+1), |
| 4972 | list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4)), |
| 4973 | (x^6+2*x^4-3*x^2)*d^2-(4*x^5-4*x^4-12*x^2-12*x)*d + |
| 4974 | (6*x^4-12*x^3-6*x^2-24*x-12),1); |
| 4975 | if (!isListEqual(expected_third,obtained_third)) |
| 4976 | { |
| 4977 | print("Test 9 for testNCfac failed."); |
| 4978 | print("Expected:\n"); |
| 4979 | print(expected_third); |
| 4980 | print("obtained:\n"); |
| 4981 | print(obtained_third); |
| 4982 | result = 0; |
| 4983 | } |
| 4984 | //Test 9: correct factorization, more than one element, incorrect second |
| 4985 | //and third parameter |
| 4986 | expected_third = list(poly(-24),poly(-24)); |
| 4987 | obtained_third = |
| 4988 | testNCfac(list(list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1), |
| 4989 | list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4)), |
| 4990 | (x^6+2*x^4-3*x^2)*d^2-(4*x^5-4*x^4-12*x^2-12*x)*d + |
| 4991 | (6*x^4-12*x^3-6*x^2-24*x+12),1); |
| 4992 | if (!isListEqual(expected_third,obtained_third)) |
| 4993 | { |
| 4994 | print("Test 9 for testNCfac failed."); |
| 4995 | print("Expected:\n"); |
| 4996 | print(expected_third); |
| 4997 | print("obtained:\n"); |
| 4998 | print(obtained_third); |
| 4999 | result = 0; |
| 5000 | } |
| 5001 | return(result); |
| 5002 | }//testing testNCfac |
| 5003 | |
| 5004 | |
| 5005 | static proc monsSmallerThan(poly e, intvec maxDegInCoordinates) |
| 5006 | "USAGE: monsSmallerThan(e, maxDegInCoordinates); e is a |
| 5007 | polynomial, but we are only interested in its leading monomial. |
| 5008 | maxDegInCoordinates encodes the maximal degree we want to encounter |
| 5009 | in each variable. |
| 5010 | RETURN: list |
| 5011 | PURPOSE: Computes all monomials in the basering which are degree-wise |
| 5012 | smaller than the leading monomial of e. |
| 5013 | "{//monsSmallerThan |
| 5014 | int p=printlevel-voice+2;//for dbprint |
| 5015 | int i; |
| 5016 | string dbprintWhitespace = ""; |
| 5017 | for (i = 1; i<=voice;i++) |
| 5018 | {dbprintWhitespace = dbprintWhitespace + " ";} |
| 5019 | list result; |
| 5020 | intvec tempIntVec = leadexp(1); |
| 5021 | while(increment_intvec(tempIntVec,maxDegInCoordinates) != tempIntVec) |
| 5022 | {//counting through all possible monomials |
| 5023 | tempIntVec = increment_intvec(tempIntVec,maxDegInCoordinates); |
| 5024 | if (monomial(tempIntVec)<leadmonom(e)) |
| 5025 | { |
| 5026 | result = insert(result, monomial(tempIntVec)); |
| 5027 | } |
| 5028 | }//counting through all possible monomials |
| 5029 | return(result); |
| 5030 | }//monsSmallerThan |
| 5031 | |
| 5032 | |
| 5033 | static proc test_monsSmallerThan() |
| 5034 | {//testing monsSmallerThan |
| 5035 | int result = 1; |
| 5036 | ring R = 0,(x,y,z,d,w),lp; |
| 5037 | //Test 1: 0 |
| 5038 | poly input1 = 0; |
| 5039 | intvec input2 = intvec(2,2,2,2,2); |
| 5040 | list expected = list(); |
| 5041 | list obtained = monsSmallerThan(input1, input2); |
| 5042 | if (!isListEqual(expected,obtained)) |
| 5043 | { |
| 5044 | print("Test 1 for monsSmallerThan failed."); |
| 5045 | print("Expected:\n"); |
| 5046 | print(expected); |
| 5047 | print("obtained:\n"); |
| 5048 | print(obtained); |
| 5049 | result = 0; |
| 5050 | } |
| 5051 | //Test 2: 1 |
| 5052 | input1 = 1; |
| 5053 | input2 = intvec(2,2,2,2,2); |
| 5054 | expected = list(); |
| 5055 | obtained = monsSmallerThan(input1, input2); |
| 5056 | if (!isListEqual(expected,obtained)) |
| 5057 | { |
| 5058 | print("Test 2 for monsSmallerThan failed."); |
| 5059 | print("Expected:\n"); |
| 5060 | print(expected); |
| 5061 | print("obtained:\n"); |
| 5062 | print(obtained); |
| 5063 | result = 0; |
| 5064 | } |
| 5065 | //Test 3: lowest monomial |
| 5066 | input1 = w; |
| 5067 | input2 = intvec(2,2,2,2,2); |
| 5068 | expected = list(); |
| 5069 | obtained = monsSmallerThan(input1, input2); |
| 5070 | if (!isListEqual(expected,obtained)) |
| 5071 | { |
| 5072 | print("Test 3 for monsSmallerThan failed."); |
| 5073 | print("Expected:\n"); |
| 5074 | print(expected); |
| 5075 | print("obtained:\n"); |
| 5076 | print(obtained); |
| 5077 | result = 0; |
| 5078 | } |
| 5079 | //Test 4: second lowest monomial |
| 5080 | input1 = d; |
| 5081 | input2 = intvec(2,2,2,2,2); |
| 5082 | expected = list(w^2,w); |
| 5083 | obtained = monsSmallerThan(input1, input2); |
| 5084 | if (!isListEqual(expected,obtained)) |
| 5085 | { |
| 5086 | print("Test 4 for monsSmallerThan failed."); |
| 5087 | print("Expected:\n"); |
| 5088 | print(expected); |
| 5089 | print("obtained:\n"); |
| 5090 | print(obtained); |
| 5091 | result = 0; |
| 5092 | } |
| 5093 | //Test 5: third lowest monomial, no second lowest |
| 5094 | input1 = z; |
| 5095 | input2 = intvec(2,2,2,0,2); |
| 5096 | expected = list(w^2,w); |
| 5097 | obtained = monsSmallerThan(input1, input2); |
| 5098 | if (!isListEqual(expected,obtained)) |
| 5099 | { |
| 5100 | print("Test 5 for monsSmallerThan failed."); |
| 5101 | print("Expected:\n"); |
| 5102 | print(expected); |
| 5103 | print("obtained:\n"); |
| 5104 | print(obtained); |
| 5105 | result = 0; |
| 5106 | } |
| 5107 | //Test 6: highest monomial, random max degrees for the others |
| 5108 | input1 = x; |
| 5109 | input2 = intvec(3,1,1,0,1); |
| 5110 | expected = list(yzw,yz,yw,y,zw,z,w); |
| 5111 | obtained = monsSmallerThan(input1, input2); |
| 5112 | if (!isListEqual(expected,obtained)) |
| 5113 | { |
| 5114 | print("Test 6 for monsSmallerThan failed."); |
| 5115 | print("Expected:\n"); |
| 5116 | print(expected); |
| 5117 | print("obtained:\n"); |
| 5118 | print(obtained); |
| 5119 | result = 0; |
| 5120 | } |
| 5121 | return (result); |
| 5122 | }//testing monsSmallerThan |
| 5123 | |
| 5124 | |
| 5125 | static proc getMaxDegreeVec(poly h) |
| 5126 | "USAGE: getMaxDegreeVec(h); h is a polynomial in the |
| 5127 | current ring. |
| 5128 | RETURN: intvec |
| 5129 | PURPOSE: Returns for each variable in the ring the maximal |
| 5130 | degree in which it appears in h. |
| 5131 | " |
| 5132 | { |
| 5133 | if (h == 0) |
| 5134 | {return(0:nvars(basering));} |
| 5135 | intvec tempIntVec1 = 0:nvars(basering); |
| 5136 | intvec maxDegrees = 0:nvars(basering); |
| 5137 | int i; |
| 5138 | for (i = 1; i <= nvars(basering); i++) |
| 5139 | {//filling maxDegrees |
| 5140 | tempIntVec1 = 0:nvars(basering); |
| 5141 | tempIntVec1[i] = 1; |
| 5142 | maxDegrees[i] = deg(h,tempIntVec1); |
| 5143 | }//filling maxDegrees |
| 5144 | return(maxDegrees); |
| 5145 | } |
| 5146 | |
| 5147 | |
| 5148 | static proc test_getMaxDegreeVec() |
| 5149 | {//testing getMaxDegreeVec |
| 5150 | int result = 1; |
| 5151 | //Test1: 0 |
| 5152 | ring R = 0,(u,v,w,x,y,z),dp; |
| 5153 | intvec expected = 0:6; |
| 5154 | intvec obtained = getMaxDegreeVec(0); |
| 5155 | if (expected!=obtained) |
| 5156 | { |
| 5157 | print("Test 1 for getMaxDegreeVec failed."); |
| 5158 | print("Expected:\n"); |
| 5159 | print(expected); |
| 5160 | print("obtained:\n"); |
| 5161 | print(obtained); |
| 5162 | result = 0; |
| 5163 | } |
| 5164 | //Test2: Constant neq 0 |
| 5165 | expected = 0:6; |
| 5166 | obtained = getMaxDegreeVec(5); |
| 5167 | if (expected!=obtained) |
| 5168 | { |
| 5169 | print("Test 2 for getMaxDegreeVec failed."); |
| 5170 | print("Expected:\n"); |
| 5171 | print(expected); |
| 5172 | print("obtained:\n"); |
| 5173 | print(obtained); |
| 5174 | result = 0; |
| 5175 | } |
| 5176 | //Test 3: univariate, first variable |
| 5177 | expected = 2,0,0,0,0,0; |
| 5178 | obtained = getMaxDegreeVec(5*u^2 + u + 1); |
| 5179 | if (expected!=obtained) |
| 5180 | { |
| 5181 | print("Test 3 for getMaxDegreeVec failed."); |
| 5182 | print("Expected:\n"); |
| 5183 | print(expected); |
| 5184 | print("obtained:\n"); |
| 5185 | print(obtained); |
| 5186 | result = 0; |
| 5187 | } |
| 5188 | //Test 4: univariate, another variable |
| 5189 | expected = 0,0,0,3,0,0; |
| 5190 | obtained = getMaxDegreeVec(5*x^3 + x^2 + 1); |
| 5191 | if (expected!=obtained) |
| 5192 | { |
| 5193 | print("Test 4 for getMaxDegreeVec failed."); |
| 5194 | print("Expected:\n"); |
| 5195 | print(expected); |
| 5196 | print("obtained:\n"); |
| 5197 | print(obtained); |
| 5198 | result = 0; |
| 5199 | } |
| 5200 | //Test 5: random polynomial |
| 5201 | expected = 3,1,2,4,3,2; |
| 5202 | obtained = getMaxDegreeVec(u^3*x^2*v*w^2*z + x^4 + y^3*z^2 + 1); |
| 5203 | if (expected!=obtained) |
| 5204 | { |
| 5205 | print("Test 5 for getMaxDegreeVec failed."); |
| 5206 | print("Expected:\n"); |
| 5207 | print(expected); |
| 5208 | print("obtained:\n"); |
| 5209 | print(obtained); |
| 5210 | result = 0; |
| 5211 | } |
| 5212 | return(result); |
| 5213 | }//testing getMaxDegreeVec |
| 5214 | |
| 5215 | |
| 5216 | static proc isFactorizationSmaller(list f1, list f2) |
| 5217 | "USAGE: isFactorizationSmallerEq(f1,f2); f1 and f2 are lists |
| 5218 | containing polynomials |
| 5219 | RETURN: bool |
| 5220 | PURPOSE: Checks entry-wise of all factorizations in f1 are smaller |
| 5221 | than the ones in f2 (lexicographic order, starting from |
| 5222 | the first position). |
| 5223 | "{//proc isFactorizationSmaller |
| 5224 | return (string(f1)<string(f2)); |
| 5225 | }//proc isFactorizationSmaller |
| 5226 | |
| 5227 | |
| 5228 | static proc test_isFactorizationSmaller() |
| 5229 | {//isFactorizationSmaller |
| 5230 | int result = 1; |
| 5231 | ring R = 0,(x,d),dp; |
| 5232 | def r = nc_algebra(1,1); |
| 5233 | setring r; |
| 5234 | //Test 1: Two equal lists, empty |
| 5235 | list input1 = list(); |
| 5236 | list input2 = list(); |
| 5237 | int expected = 0; |
| 5238 | int obtained = isFactorizationSmaller(input1,input2); |
| 5239 | if (expected!=obtained) |
| 5240 | { |
| 5241 | print("Test 1 for isFactorizationSmaller failed."); |
| 5242 | print("Expected:\n"); |
| 5243 | print(expected); |
| 5244 | print("obtained:\n"); |
| 5245 | print(obtained); |
| 5246 | result = 0; |
| 5247 | } |
| 5248 | //Test 2: Two not equal lists, first one is empty |
| 5249 | input1 = list(1,2,3); |
| 5250 | input2 = list(); |
| 5251 | expected = 0; |
| 5252 | obtained = isFactorizationSmaller(input1,input2); |
| 5253 | if (expected!=obtained) |
| 5254 | { |
| 5255 | print("Test 2 for isFactorizationSmaller failed."); |
| 5256 | print("Expected:\n"); |
| 5257 | print(expected); |
| 5258 | print("obtained:\n"); |
| 5259 | print(obtained); |
| 5260 | result = 0; |
| 5261 | } |
| 5262 | //Test 3: Two not equal lists, second one is empty |
| 5263 | input1 = list(); |
| 5264 | input2 = list(1,2,3); |
| 5265 | expected = 1; |
| 5266 | obtained = isFactorizationSmaller(input1,input2); |
| 5267 | if (expected!=obtained) |
| 5268 | { |
| 5269 | print("Test 3 for isFactorizationSmaller failed."); |
| 5270 | print("Expected:\n"); |
| 5271 | print(expected); |
| 5272 | print("obtained:\n"); |
| 5273 | print(obtained); |
| 5274 | result = 0; |
| 5275 | } |
| 5276 | //Test 4: Two different factorizations, real ones |
| 5277 | input1 = list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1); |
| 5278 | input2 = list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4); |
| 5279 | expected = 0; |
| 5280 | obtained = isFactorizationSmaller(input1,input2); |
| 5281 | if (expected!=obtained) |
| 5282 | { |
| 5283 | print("Test 4 for isFactorizationSmaller failed."); |
| 5284 | print("Expected:\n"); |
| 5285 | print(expected); |
| 5286 | print("obtained:\n"); |
| 5287 | print(obtained); |
| 5288 | result = 0; |
| 5289 | } |
| 5290 | //Test 5: Same as test 4, but reversed |
| 5291 | input1 = list(1,x4d+x3d-4x3+3x2d-3x2+3xd-6x-3,x2d-xd-2x+4); |
| 5292 | input2 = list(1,x4d-x3d-3x3+3x2d+6x2-3xd-3x+12,x2d+xd-3x-1); |
| 5293 | expected = 1; |
| 5294 | obtained = isFactorizationSmaller(input1,input2); |
| 5295 | if (expected!=obtained) |
| 5296 | { |
| 5297 | print("Test 5 for isFactorizationSmaller failed."); |
| 5298 | print("Expected:\n"); |
| 5299 | print(expected); |
| 5300 | print("obtained:\n"); |
| 5301 | print(obtained); |
| 5302 | result = 0; |
| 5303 | } |
| 5304 | return(result); |
| 5305 | }//testing isFactorizationSmaller |
| 5306 | |
| 5307 | |
| 5308 | static proc sortedInsert(list newFact, list factList) |
| 5309 | "USAGE: sortedInsert(newFact, factList); newFact is a list that |
| 5310 | represents a factorization of a certain polynomial, and factList is a |
| 5311 | list containing several different factorizations of the same |
| 5312 | polynomial. |
| 5313 | RETURN: list(list) |
| 5314 | PURPOSE: Inserts newFact into factList, if not yet contained in |
| 5315 | factList. |
| 5316 | "{//proc sortedInsert |
| 5317 | int first = 1; |
| 5318 | int last = size(factList); |
| 5319 | int middle; |
| 5320 | while (first <= last) |
| 5321 | { |
| 5322 | middle = first + ((last - first) div 2); |
| 5323 | if (isFactorizationSmaller(factList[middle], newFact)) |
| 5324 | { |
| 5325 | first = middle + 1; |
| 5326 | } |