| 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 | } |
