cheuberg commented 9 years ago

In [HKP2015], we study the sum of output of a transducer when reading a random non-negative integer up to a certain N. Under suitable conditions, it has a periodic fluctuation in the second order term. In that paper, we compute the Fourier coefficients of this periodic fluctuation. This ticket holds the corresponding Sage code.

Depends on #16747 Depends on #17194 Depends on #17198 Depends on #17218 Depends on #17220 Depends on #17221

CC: @sagetrac-skropf @dkrenn

Component: finite state machines

Keywords: Fourier coefficients

Author: Clemens Heuberger, Sara Kropf

Branch/Commit: u/cheuberg/fsm/fourier_2 @ 19e274b

Reviewer: Sara Kropf

Issue created by migration from https://trac.sagemath.org/ticket/17222

cheuberg commented 9 years ago

Branch: u/cheuberg/fsm/fourier

cheuberg commented 9 years ago

Commit: ab8784b

cheuberg commented 9 years ago

Dependencies: #16747, #17194, #17198, #17218, #17220, #17221

cheuberg commented 9 years ago

Changed keywords from none to Fourier coefficients

cheuberg commented 9 years ago

Last 10 new commits:

`a9a015c`	`Trac #17222: Fix numerical noise in doctests after last commit`
`7bcc838`	`Trac #17222: Do not insist on small relative approximation error`
`75403f5`	`Trac #17222: Fix numerical noise after commit 7bcc83`
`db95ccc`	`Trac #17222: Remove obsolete methods`
`661fd25`	`Trac #17222: remove "long time" from doctests`
`c5b591f`	`Trac #17222: Uniform handling of CIF precision`
`836d0ea`	`Trac #17222: Documentation updates`
`f4d4660`	`Trac #17222: Insert File Header`
`5a6e26d`	`Trac #17222: Rename classes and methods`
`ab8784b`	`Trac #17222: Mark almost all doctests as # optional - arb`

cheuberg commented 9 years ago

Changed commit from ab8784b to 85836e1

cheuberg commented 9 years ago

Changed branch from u/cheuberg/fsm/fourier to u/cheuberg/fsm/fourier_2

cheuberg commented 9 years ago

comment:3

Rebased branch such that the full history of the branch is now correctly shown.

Last 10 new commits:

`6971dce`	`Trac #17222: Fix numerical noise in doctests after last commit`
`67b7915`	`Trac #17222: Do not insist on small relative approximation error`
`26ece84`	`Trac #17222: Fix numerical noise after commit 7bcc83`
`74bbdd0`	`Trac #17222: Remove obsolete methods`
`9abef6c`	`Trac #17222: remove "long time" from doctests`
`af02e2a`	`Trac #17222: Uniform handling of CIF precision`
`08382c8`	`Trac #17222: Documentation updates`
`a3925bf`	`Trac #17222: Insert File Header`
`7a8e7f7`	`Trac #17222: Rename classes and methods`
`85836e1`	`Trac #17222: Mark almost all doctests as # optional - arb`

cheuberg commented 9 years ago

comment:4

In commit 27080b5 "Trac #17198: Rewrote methods .min and .max to handle more than two elements" in #17198, the proposed functions min_RIF and max_RIF are removed. This needs to be merged into this ticket and the code in this ticket has to be adapted accordingly. I refrain from doing so as long as the fate of the patch in #17198 is not clear.

cheuberg commented 9 years ago

comment:5

17198 is now positively reviewed, so the changes should be incorporated here.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`27080b5`	`Trac #17198: Rewrote methods .min and .max to handle more than two elements`
`8fe46d0`	`Merge branch 'u/cheuberg/rings/RIF-min-max' (#17198) of git://trac.sagemath.org/sage into fsm/fourier_2`
`2e94424`	`Trac #17222: Adapt code after #17198`
`9af5402`	`Trac #17222: Replace definitions of three transducers`
`5189968`	`Trac #17222: remove comparison with old code`
`ff2c06a`	`Trac #17222: remove fsm_fourier from documentation`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 85836e1 to ff2c06a

cheuberg commented 9 years ago

comment:7

Replying to @cheuberg:

17198 is now positively reviewed, so the changes should be incorporated here.

Done.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`aeaebf1`	`Trac #17221: replace "coercion" by "conversion" where appropriate`
`969160c`	`Trac #17221: range(base.abs()) --> srange(base.abs())`
`f891643`	`Trac #17221: remove "Python int" from docstring`
`83f1c03`	`Trac #17221: Replace example on binary sum of digits by weight of ternary expansion`
`aa37aaf`	Trac #17221: Move examples on ``output_rings`` to the end
`9594dca`	`Trac #17221: More explanations on the NAF, concrete examples`
`446f8f4`	`Trac #17221: Allow alternative input format (rules)`
`25e02eb`	`Trac #17221: Allow negative residues r in recursion rules.`
`448a2fc`	`Merge branch 'fsm/generator-recursion' into fsm/fourier_2`
`fadf152`	`Trac #17222: Update doctests`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from ff2c06a to fadf152

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`1196b57`	`Trac #17194: Fix RealBallField._an_element_`
`195a6ee`	`Trac #17194: Fix two broken references`
`5166337`	`Trac #17218: Merge #17194`
`1b39b15`	`Trac #17218: rename module to complex_ball_acb`
`ceeb591`	`Trac #17218: Fix doctests after renaming modules`
`fa46546`	`Trac #17218: implement parent`
`2f7c032`	`Trac #17220: Merge #17218 branch due to incompatible changes`
`3b7cd32`	`Trac #17220: Fix code after merge; acb_mat_to_matrix takes CIF`
`2266f9a`	`Trac #17222: Merge #17220 due to incompatible changes`
`d9a60b8`	`Trac #17222: Fix code after merge`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from fadf152 to d9a60b8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from d9a60b8 to 743a5aa

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`f40aaef`	`Trac #17218: Change signature of acb_to_ComplexIntervalFieldElement`
`dacd766`	`Merge #17218 due to conflicting change in commit f40aaef`
`fda400e`	`Trac #17220: Fix code after merge`
`2efc505`	`Trac #17218: let ComplexBallField belong to Fields()`
`e1dd21a`	`Trac #17220: Merge #17218`
`06bcc68`	`Trac #17220: rename matrix_acb_dense to matrix_complex_ball_dense`
`68d673b`	`Trac #17220: acb_mat as Sage matrix --- Level 1 functionality`
`48e0518`	`Trac #17222: Merge #17220 due to incompatible change`
`743a5aa`	`Trac #17222: Adapt code after merge of #17220`

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 9 years ago

Changed branch from u/cheuberg/fsm/fourier_2 to u/skropf/fsm/fourier_2

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 9 years ago

comment:12

All tests pass, the documentation is fine for me and the code corresponds to the results in the original paper. From my side, this is a positive review.

New commits:

5f574b4 Ticket 17222: Small corrections in the documentation

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 9 years ago

Changed commit from 743a5aa to 5f574b4

c50b3d32-6cb1-4b90-a060-6a332e54ef6a commented 9 years ago

Reviewer: Sara Kropf

cheuberg commented 9 years ago

Changed commit from 5f574b4 to 9db5332

cheuberg commented 9 years ago

Changed branch from u/skropf/fsm/fourier_2 to u/cheuberg/fsm/fourier_2

cheuberg commented 9 years ago

comment:13

Merge #17220 due to merge conflict with #18145.

New commits:

`cbce806`	`Trac #17220: mark three doctests as optional - arb`
`1e0608c`	`Merge tag '6.6.beta5' into rings/complex_interval_acb`
`ef6ae7b`	`Trac #17218: Fix doctests after merge of 6.6.beta5 (and therefore #17786)`
`87bbb16`	`Trac #17218: Fix indendations`
`0e3a82e`	`Trac #17218: Merge '6.7.beta1' due to merge conflict with #18145`
`1a8e8dc`	`Trac #17220: Merge branch #17218 due to merge conflict with #18145`
`9db5332`	`Trac #17222: Merge branch #17220 due to merge conflict with #18145`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

7b5aba3 Trac #17222: Merge 6.7.beta3 in order to resolve merge conflict with #17662

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 9db5332 to 7b5aba3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 7b5aba3 to 3001632

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`1c6123c`	`Small correction in the documentation`
`556651a`	`Trac #17220: merge latest version of #17220`
`1dd4c89`	`Trac #17220: Adapt doctest to include FutureWarning`
`f96ee48`	`Trac #17220: Add doctest for __richcmp__`
`afc6d7b`	`Trac #17220: Merge 6.8.beta8`
`95a0798`	`Trac #17220: Remove flint_depends`
`a22a79e`	`Trac #17222: Merge latest version of #17220`
`3001632`	`Trac #17222: Remove 'flint_depends'`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 3001632 to f3a5065

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

f3a5065 Trac #17222: Update reference [HKP2014] to [HKP2015]

cheuberg commented 9 years ago

Description changed:

--- 
+++ 
@@ -1 +1 @@
-In a forthcoming paper (Clemens Heuberger, Sara Kropf, and Helmut Prodinger, Asymptotic analysis of the sum of the output of transducers), we study the sum of output of a transducer when reading a random non-negative integer up to a certain N. Under suitable conditions, it has a periodic fluctuation in the second order term. In that paper, we compute the Fourier coefficients of this periodic fluctuation. This ticket shall hold the corresponding Sage code.
+In [HKP2015], we study the sum of output of a transducer when reading a random non-negative integer up to a certain N. Under suitable conditions, it has a periodic fluctuation in the second order term. In that paper, we compute the Fourier coefficients of this periodic fluctuation. This ticket holds the corresponding Sage code.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`f50c239`	`Merge tag '6.9.beta0' into fsm/fourier_2`
`95f02db`	`Trac #17222: remove FSMOldProcessOutput`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from f3a5065 to 95f02db

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

c79211e Trac #17222: make doctest deterministic

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 95f02db to c79211e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`650dff3`	`Trac #17220: Fix imports and doctests after merge of #19152`
`db6bde9`	`Trac #17220: remove superfluous imports in doctests after #19152`
`2190aa4`	`Trac #17220: Fix import of ComplexBallField, add doctest`
`b3a2a08`	`Trac #17220: Fix documentation`
`867803f`	`Trac #17220: Include documentation of complex arb matrices`
`4f62231`	`Trac #17222: Merge #17220`
`897f2b4`	`Trac #17222: Fix imports after #19152`
`a820e2d`	`Trac #17222: Remove "optional arb" doctest flags, as arb is now standard`
`de60720`	`Trac #17222: include fsm_fourier into documentation`
`d90c932`	`Trac #17222: Remove obsolete TODO`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from c79211e to d90c932

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`83b7409`	`Merge tag '6.10.beta6' into matrix/acb_dense`
`832f728`	Trac #17220: Remove `__richcmp__` (_richcmp does no longer exist)
`7ee8bf4`	`Merge branch 'matrix/acb_dense' into fsm/fourier_2`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from d90c932 to 7ee8bf4

cheuberg commented 8 years ago

Work Issues: merge #17220

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`0f5246d`	`#17220 rm duplicate declarations`
`3e53d94`	`#17220 cython style`
`444dea4`	`#17220 update matrix/docs.py for Matrix_complex_ball_dense`
`41263f0`	`#17220 cosmetic fixes + a few tests`
`0e3c4ce`	`Trac #17220: Change title for documentation`
`a56cab1`	Trac #17220: modify logic of `__init__` to match that of generic_dense
`b1fbfb1`	`Trac #17220: clarify parameter "copy"`
`c095ddd`	`Trac #17220: Remove functions matrix_to_acb_mat and acb_mat_to_matrix`
`e3c9213`	`Trac #17222: Merge #17220`
`19e274b`	`Trac #17222: Fix code after merge of #17220`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 7ee8bf4 to 19e274b

cheuberg commented 8 years ago

comment:25

Merged latest version of #17220 (without functions matrix_to_acb_mat and acb_mat_to_matrix) and adapted code.

Now that complex balls are fully implemented, it might make sense to do all computations in complex balls; this might lead to clearer code than the current mixture of complex intervals and direct calls to arb.

cheuberg commented 8 years ago

Changed work issues from merge #17220 to none

sagemath / sage

Fourier coefficients of the fluctuation of the output sum of a transducer #17222

17198 is now positively reviewed, so the changes should be incorporated here.

17198 is now positively reviewed, so the changes should be incorporated here.