diff options
Diffstat (limited to 'src/wallsolve.ml')
| -rw-r--r-- | src/wallsolve.ml | 82 |
1 files changed, 51 insertions, 31 deletions
diff --git a/src/wallsolve.ml b/src/wallsolve.ml index 1e0e8e2..a626ab4 100644 --- a/src/wallsolve.ml +++ b/src/wallsolve.ml @@ -17,17 +17,21 @@ let anon_fun item = let input_immediate items = - if Array.length !input_seq > 0 - then (prerr_endline "Error: Multiple input sequences specified"; exit 2) - else try input_seq := Util.read_integer_list items + if Array.length !input_seq > 0 then + (prerr_endline "Error: Multiple input sequences specified"; + exit 2) + else + try input_seq := Util.read_integer_list items with Util.Not_an_integer s -> prerr_endline ("Error: The argument '" ^ s ^ "' is not an integer"); exit 2 let input_from_file filename = - if Array.length !input_seq > 0 - then (prerr_endline "Error: Multiple input sequences specified"; exit 2) - else try input_seq := Util.read_sequence_file filename + if Array.length !input_seq > 0 then + (prerr_endline "Error: Multiple input sequences specified"; + exit 2) + else + try input_seq := Util.read_sequence_file filename with Util.Not_an_integer s -> prerr_endline ("Error: The item '" ^ s ^ "' from file '" ^ filename ^ "' is not an integer"); exit 2 @@ -58,29 +62,39 @@ module My_Wall = Wall.Make (My_Algebra) let _ = - if Array.length Sys.argv <= 1 then (Arg.usage speclist usage_msg; exit 1); + if Array.length Sys.argv <= 1 then + (Arg.usage speclist usage_msg; + exit 1); + Arg.parse speclist anon_fun usage_msg; - if Array.length !input_seq = 0 then (prerr_endline "Error: No input sequence provided"; exit 2); - if Array.length !input_seq < 2 - then (prerr_endline "Error: Input sequence not long enough to solve"; exit 2); + if Array.length !input_seq = 0 then + (prerr_endline "Error: No input sequence provided"; + exit 2); + + if Array.length !input_seq < 2 then + (prerr_endline "Error: Input sequence not long enough to solve"; + exit 2); (* Convert input integer sequence into the right sort of input polynomial sequence. *) let poly_offset n = Poly.of_list [(Z.neg !input_seq.(n), Z.one); (!input_seq.(n+1), Z.zero)] in - let poly_inputs = Array.init (Array.length !input_seq - 1) poly_offset in + let poly_inputs = + Array.init (Array.length !input_seq - 1) poly_offset in (* Generate the number wall and look at the bottom most non-zero row. *) - let scribbles = My_Wall.create - ~dimx:(Array.length poly_inputs) - ~dimy:!depth_limit - ~init:poly_inputs in + let scribbles = + My_Wall.create + ~dimx:(Array.length poly_inputs) + ~dimy:!depth_limit + ~init:poly_inputs in let row_of_interest = My_Wall.last_nonzero_row scribbles in (* Test whether there is actually a row of zeros under the row of interest. *) - if row_of_interest = My_Wall.y_length scribbles - 1 - then (prerr_endline "Error: Depth limit too low to solve sequence"; exit 2); + if row_of_interest = My_Wall.y_length scribbles - 1 then + (prerr_endline "Error: Depth limit too low to solve sequence"; + exit 2); (* Test whether the row of interest has enough entries to be sure of them all being the same. *) let exists_pred x = @@ -89,8 +103,9 @@ let _ = Array.fold_left ( + ) 0 in let naturals_to n = Array.init n (fun n -> n) in - if array_sum (Array.map exists_pred (naturals_to (My_Wall.x_length scribbles))) < 3 - then (prerr_endline "Error: Input sequence not long enough to solve"; exit 2); + if array_sum (Array.map exists_pred (naturals_to (My_Wall.x_length scribbles))) < 3 then + (prerr_endline "Error: Input sequence not long enough to solve"; + exit 2); (* Need to normalize the polynomials in the row as if they were set equal to zero. *) let rec gcd a b = @@ -111,17 +126,20 @@ let _ = ~y:row_of_interest) in (* Check for degeneracy. *) - if Poly.degree key_poly = Z.zero - then (prerr_endline "Error: Result is degree zero, not sure how that happened"; exit 2); + if Poly.degree key_poly = Z.zero then + (prerr_endline "Error: Result is degree zero, not sure how that happened"; + exit 2); (* Check that all the polynomials in the row of interest are equal once normalized. *) let equals_pred x = let value = My_Wall.get_opt scribbles ~x ~y:row_of_interest in - if Option.is_some value - then normalize (Option.get value) = key_poly - else true in - if not (Array.for_all equals_pred (naturals_to (My_Wall.x_length scribbles))) - then (prerr_endline "Error: Polynomials differ, maybe try a longer sequence?"; exit 2); + if Option.is_some value then + normalize (Option.get value) = key_poly + else + true in + if not (Array.for_all equals_pred (naturals_to (My_Wall.x_length scribbles))) then + (prerr_endline "Error: Polynomials differ, maybe try a longer sequence?"; + exit 2); (* Print out the polynomial as if it was a recurrence relation with the highest degree term *) (* being on the left hand side and the remaining terms being on the right hand side. *) @@ -141,17 +159,19 @@ let _ = print_newline (); (* This... should probably never trigger, but might as well check anyway. *) - if Poly.degree key_poly > Z.of_int (Array.length !input_seq) - then (prerr_endline "Error: Recurrence relation longer than input sequence... wtfhow?"; exit 2); + if Poly.degree key_poly > Z.of_int (Array.length !input_seq) then + (prerr_endline "Error: Recurrence relation longer than input sequence... wtfhow?"; + exit 2); (* Calculate and print the predicted next number of the input sequence. *) let calc_next p inp = let lhs = List.hd p in let rhs = List.map (fun (x,y) -> (Z.neg x, y)) (List.tl p) in let rec process result terms = - if terms = [] - then result - else let current = List.hd terms in + if terms = [] then + result + else + let current = List.hd terms in let index = Array.length inp - Z.(to_int (snd lhs - snd current)) in process Z.(result + fst current * inp.(index)) (List.tl terms) in Z.div (process Z.zero rhs) (fst lhs) in |