324 lemma bin_sign_rest [simp]: |
324 lemma bin_sign_rest [simp]: |
325 "bin_sign (bin_rest w) = bin_sign w" |
325 "bin_sign (bin_rest w) = bin_sign w" |
326 by (cases w rule: bin_exhaust) auto |
326 by (cases w rule: bin_exhaust) auto |
327 |
327 |
328 primrec bintrunc :: "nat \<Rightarrow> int \<Rightarrow> int" where |
328 primrec bintrunc :: "nat \<Rightarrow> int \<Rightarrow> int" where |
329 Z : "bintrunc 0 bin = Int.Pls" |
329 Z : "bintrunc 0 bin = 0" |
330 | Suc : "bintrunc (Suc n) bin = bintrunc n (bin_rest bin) BIT (bin_last bin)" |
330 | Suc : "bintrunc (Suc n) bin = bintrunc n (bin_rest bin) BIT (bin_last bin)" |
331 |
331 |
332 primrec sbintrunc :: "nat => int => int" where |
332 primrec sbintrunc :: "nat => int => int" where |
333 Z : "sbintrunc 0 bin = |
333 Z : "sbintrunc 0 bin = (case bin_last bin of (1::bit) \<Rightarrow> -1 | (0::bit) \<Rightarrow> 0)" |
334 (case bin_last bin of (1::bit) => Int.Min | (0::bit) => Int.Pls)" |
|
335 | Suc : "sbintrunc (Suc n) bin = sbintrunc n (bin_rest bin) BIT (bin_last bin)" |
334 | Suc : "sbintrunc (Suc n) bin = sbintrunc n (bin_rest bin) BIT (bin_last bin)" |
336 |
335 |
337 lemma [code]: |
336 lemma sign_bintr: "bin_sign (bintrunc n w) = 0" |
338 "sbintrunc 0 bin = |
|
339 (case bin_last bin of (1::bit) => - 1 | (0::bit) => 0)" |
|
340 "sbintrunc (Suc n) bin = sbintrunc n (bin_rest bin) BIT (bin_last bin)" |
|
341 apply simp_all |
|
342 apply (simp only: Pls_def Min_def) |
|
343 done |
|
344 |
|
345 lemma sign_bintr: "bin_sign (bintrunc n w) = Int.Pls" |
|
346 by (induct n arbitrary: w) auto |
337 by (induct n arbitrary: w) auto |
347 |
338 |
348 lemma bintrunc_mod2p: "bintrunc n w = (w mod 2 ^ n)" |
339 lemma bintrunc_mod2p: "bintrunc n w = (w mod 2 ^ n)" |
349 apply (induct n arbitrary: w) |
340 apply (induct n arbitrary: w) |
350 apply (simp add: Pls_def) |
341 apply simp |
351 apply (simp add: bin_last_def bin_rest_def Bit_def zmod_zmult2_eq) |
342 apply (simp add: bin_last_def bin_rest_def Bit_def zmod_zmult2_eq) |
352 done |
343 done |
353 |
344 |
354 lemma sbintrunc_mod2p: "sbintrunc n w = (w + 2 ^ n) mod 2 ^ (Suc n) - 2 ^ n" |
345 lemma sbintrunc_mod2p: "sbintrunc n w = (w + 2 ^ n) mod 2 ^ (Suc n) - 2 ^ n" |
355 apply (induct n arbitrary: w) |
346 apply (induct n arbitrary: w) |
356 apply clarsimp |
347 apply clarsimp |
357 apply (subst mod_add_left_eq) |
348 apply (subst mod_add_left_eq) |
358 apply (simp add: bin_last_def) |
349 apply (simp add: bin_last_def) |
359 apply (simp add: number_of_eq) |
350 apply simp |
360 apply (simp add: Pls_def) |
351 apply (simp add: bin_last_def bin_rest_def Bit_def) |
361 apply (simp add: bin_last_def bin_rest_def Bit_def |
|
362 cong: number_of_False_cong) |
|
363 apply (clarsimp simp: mod_mult_mult1 [symmetric] |
352 apply (clarsimp simp: mod_mult_mult1 [symmetric] |
364 zmod_zdiv_equality [THEN diff_eq_eq [THEN iffD2 [THEN sym]]]) |
353 zmod_zdiv_equality [THEN diff_eq_eq [THEN iffD2 [THEN sym]]]) |
365 apply (rule trans [symmetric, OF _ emep1]) |
354 apply (rule trans [symmetric, OF _ emep1]) |
366 apply auto |
355 apply auto |
367 apply (auto simp: even_def) |
356 apply (auto simp: even_def) |
368 done |
357 done |
369 |
358 |
370 subsection "Simplifications for (s)bintrunc" |
359 subsection "Simplifications for (s)bintrunc" |
371 |
360 |
372 lemma bintrunc_n_0 [simp]: "bintrunc n 0 = 0" |
361 lemma bintrunc_n_0 [simp]: "bintrunc n 0 = 0" |
373 by (induct n) (auto simp add: Int.Pls_def) |
362 by (induct n) auto |
374 |
363 |
375 lemma sbintrunc_n_0 [simp]: "sbintrunc n 0 = 0" |
364 lemma sbintrunc_n_0 [simp]: "sbintrunc n 0 = 0" |
376 by (induct n) (auto simp add: Int.Pls_def) |
365 by (induct n) auto |
377 |
366 |
378 lemma sbintrunc_n_minus1 [simp]: "sbintrunc n -1 = -1" |
367 lemma sbintrunc_n_minus1 [simp]: "sbintrunc n -1 = -1" |
379 by (induct n) (auto, simp add: number_of_is_id) |
368 by (induct n) auto |
380 |
369 |
381 lemma bintrunc_Suc_numeral: |
370 lemma bintrunc_Suc_numeral: |
382 "bintrunc (Suc n) 1 = 1" |
371 "bintrunc (Suc n) 1 = 1" |
383 "bintrunc (Suc n) -1 = bintrunc n -1 BIT 1" |
372 "bintrunc (Suc n) -1 = bintrunc n -1 BIT 1" |
384 "bintrunc (Suc n) (number_of (Int.Bit0 w)) = bintrunc n (number_of w) BIT 0" |
373 "bintrunc (Suc n) (number_of (Int.Bit0 w)) = bintrunc n (number_of w) BIT 0" |
387 |
376 |
388 lemma sbintrunc_0_numeral [simp]: |
377 lemma sbintrunc_0_numeral [simp]: |
389 "sbintrunc 0 1 = -1" |
378 "sbintrunc 0 1 = -1" |
390 "sbintrunc 0 (number_of (Int.Bit0 w)) = 0" |
379 "sbintrunc 0 (number_of (Int.Bit0 w)) = 0" |
391 "sbintrunc 0 (number_of (Int.Bit1 w)) = -1" |
380 "sbintrunc 0 (number_of (Int.Bit1 w)) = -1" |
392 by (simp_all, unfold Pls_def number_of_is_id, simp_all) |
381 by simp_all |
393 |
382 |
394 lemma sbintrunc_Suc_numeral: |
383 lemma sbintrunc_Suc_numeral: |
395 "sbintrunc (Suc n) 1 = 1" |
384 "sbintrunc (Suc n) 1 = 1" |
396 "sbintrunc (Suc n) (number_of (Int.Bit0 w)) = sbintrunc n (number_of w) BIT 0" |
385 "sbintrunc (Suc n) (number_of (Int.Bit0 w)) = sbintrunc n (number_of w) BIT 0" |
397 "sbintrunc (Suc n) (number_of (Int.Bit1 w)) = sbintrunc n (number_of w) BIT 1" |
386 "sbintrunc (Suc n) (number_of (Int.Bit1 w)) = sbintrunc n (number_of w) BIT 1" |
401 "(b = (b' = (1::bit))) = (b' = (if b then (1::bit) else (0::bit)))" |
390 "(b = (b' = (1::bit))) = (b' = (if b then (1::bit) else (0::bit)))" |
402 by (cases b') auto |
391 by (cases b') auto |
403 |
392 |
404 lemmas bit_bool1 [simp] = refl [THEN bit_bool [THEN iffD1], symmetric] |
393 lemmas bit_bool1 [simp] = refl [THEN bit_bool [THEN iffD1], symmetric] |
405 |
394 |
406 lemma bin_sign_lem: "(bin_sign (sbintrunc n bin) = Int.Min) = bin_nth bin n" |
395 lemma bin_sign_lem: "(bin_sign (sbintrunc n bin) = -1) = bin_nth bin n" |
407 apply (induct n arbitrary: bin) |
396 apply (induct n arbitrary: bin) |
408 apply (case_tac bin rule: bin_exhaust, case_tac b, auto)+ |
397 apply (case_tac bin rule: bin_exhaust, case_tac b, auto)+ |
409 done |
398 done |
410 |
399 |
411 lemma nth_bintr: "bin_nth (bintrunc m w) n = (n < m & bin_nth w n)" |
400 lemma nth_bintr: "bin_nth (bintrunc m w) n = (n < m & bin_nth w n)" |
514 |
503 |
515 lemmas sbintrunc_0_BIT_B1 [simp] = |
504 lemmas sbintrunc_0_BIT_B1 [simp] = |
516 sbintrunc.Z [where bin="w BIT (1::bit)", |
505 sbintrunc.Z [where bin="w BIT (1::bit)", |
517 simplified bin_last_simps bin_rest_simps bit.simps] for w |
506 simplified bin_last_simps bin_rest_simps bit.simps] for w |
518 |
507 |
519 lemma sbintrunc_0_Bit0 [simp]: "sbintrunc 0 (Int.Bit0 w) = Int.Pls" |
508 lemma sbintrunc_0_Bit0 [simp]: "sbintrunc 0 (Int.Bit0 w) = 0" |
520 using sbintrunc_0_BIT_B0 by simp |
509 using sbintrunc_0_BIT_B0 by simp |
521 |
510 |
522 lemma sbintrunc_0_Bit1 [simp]: "sbintrunc 0 (Int.Bit1 w) = Int.Min" |
511 lemma sbintrunc_0_Bit1 [simp]: "sbintrunc 0 (Int.Bit1 w) = -1" |
523 using sbintrunc_0_BIT_B1 by simp |
512 using sbintrunc_0_BIT_B1 by simp |
524 |
513 |
525 lemmas sbintrunc_0_simps = |
514 lemmas sbintrunc_0_simps = |
526 sbintrunc_Pls sbintrunc_Min sbintrunc_0_BIT_B0 sbintrunc_0_BIT_B1 |
515 sbintrunc_Pls sbintrunc_Min sbintrunc_0_BIT_B0 sbintrunc_0_BIT_B1 |
527 sbintrunc_0_Bit0 sbintrunc_0_Bit1 |
516 sbintrunc_0_Bit0 sbintrunc_0_Bit1 |
542 lemmas sbintrunc_minus_simps = |
531 lemmas sbintrunc_minus_simps = |
543 sbintrunc_Sucs [THEN [2] sbintrunc_minus [symmetric, THEN trans]] |
532 sbintrunc_Sucs [THEN [2] sbintrunc_minus [symmetric, THEN trans]] |
544 |
533 |
545 lemma bintrunc_n_Pls [simp]: |
534 lemma bintrunc_n_Pls [simp]: |
546 "bintrunc n Int.Pls = Int.Pls" |
535 "bintrunc n Int.Pls = Int.Pls" |
547 by (induct n) (auto simp: BIT_simps) |
536 unfolding Pls_def by simp |
548 |
537 |
549 lemma sbintrunc_n_PM [simp]: |
538 lemma sbintrunc_n_PM [simp]: |
550 "sbintrunc n Int.Pls = Int.Pls" |
539 "sbintrunc n Int.Pls = Int.Pls" |
551 "sbintrunc n Int.Min = Int.Min" |
540 "sbintrunc n Int.Min = Int.Min" |
552 by (induct n) (auto simp: BIT_simps) |
541 unfolding Pls_def Min_def by simp_all |
553 |
542 |
554 lemmas thobini1 = arg_cong [where f = "%w. w BIT b"] for b |
543 lemmas thobini1 = arg_cong [where f = "%w. w BIT b"] for b |
555 |
544 |
556 lemmas bintrunc_BIT_I = trans [OF bintrunc_BIT thobini1] |
545 lemmas bintrunc_BIT_I = trans [OF bintrunc_BIT thobini1] |
557 lemmas bintrunc_Min_I = trans [OF bintrunc_Min thobini1] |
546 lemmas bintrunc_Min_I = trans [OF bintrunc_Min thobini1] |
821 [THEN rco_lem [THEN fun_cong], unfolded o_def] |
810 [THEN rco_lem [THEN fun_cong], unfolded o_def] |
822 |
811 |
823 subsection {* Splitting and concatenation *} |
812 subsection {* Splitting and concatenation *} |
824 |
813 |
825 primrec bin_split :: "nat \<Rightarrow> int \<Rightarrow> int \<times> int" where |
814 primrec bin_split :: "nat \<Rightarrow> int \<Rightarrow> int \<times> int" where |
826 Z: "bin_split 0 w = (w, Int.Pls)" |
815 Z: "bin_split 0 w = (w, 0)" |
827 | Suc: "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w) |
816 | Suc: "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w) |
828 in (w1, w2 BIT bin_last w))" |
817 in (w1, w2 BIT bin_last w))" |
829 |
818 |
830 lemma [code]: |
819 lemma [code]: |
831 "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w) in (w1, w2 BIT bin_last w))" |
820 "bin_split (Suc n) w = (let (w1, w2) = bin_split n (bin_rest w) in (w1, w2 BIT bin_last w))" |