Virgile Adam
email: virgile.adam@ibs.fr

Romain Berardozzi

Martin Byrdin

Dominique Bourgeois
email: dominique.bourgeois@ibs.fr

Phototransformable fluorescent proteins: future challenges

Keywords: dSTORM, Direct stochastic optical reconstruction microscopy, (E)GFP, (Enhanced) green fluorescent protein, FP, Fluorescent protein, LOV, Light, oxygen, or voltage-sensing flavoprotein, MEA, Monoethanolamine, PAFP, Photoactivatable fluorescent protein, PA-GFP, Photoactivatable green fluorescent protein, PALM, Photoactivated Localization microscopy, PCFP, Photoconvertible fluorescent protein, Pfr, Phytochrome far-red, Pr, Phytochrome red, Pol II, RNA polymerase II, PTFP, Phototransformable fluorescent protein, RESOLFT, Reversible saturable optical fluorescence transitions, RFP, Red fluorescent protein, RNA, Ribonucleic acid, RSFP, Reversible switchable fluorescent protein, CTPALM, Time-correlated photoactivated localization microscopy, CTPA, Consecutive Two-photon absorption, UV, Ultra-violet, XFEL, X-ray free electron laser

In fluorescence microscopy, the photophysical properties of the fluorescent markers play a fundamental role. The beauty of phototransformable fluorescent proteins (PTFPs) is that some of these properties can be precisely controlled by light. A wide range of PTFPs have been developed in recent years, including photoactivatable, photoconvertible and photoswitchable fluorescent proteins. These smart labels triggered a plethora of advanced fluorescence methods to scrutinize biological cells or organisms dynamically, quantitatively and with unprecedented resolution. Despite continuous improvements, PTFPs still suffer from limitations, and mechanistic questions remain as to how these proteins precisely work.

Introduction

Fluorescent proteins are central to biology, allowing specific, multicolor and nondisruptive labeling in living cells, tissues and whole organisms [START_REF] Dedecker | Fluorescent proteins: shine on, you crazy diamond[END_REF][START_REF] Nienhaus | Fluorescent proteins for live-cell imaging with superresolution[END_REF]. Yet, they display highly complex photophysics. For example, it was shown that GFP itself can undergo photoactivation [START_REF] Van Thor | Phototransformation of green fluorescent protein with UV and visible light leads to decarboxylation of glutamate 222[END_REF], photoconversion [START_REF] Elowitz | Photoactivation turns green fluorescent protein red[END_REF] and photoswitching [START_REF] Sinnecker | Reversible photobleaching of enhanced green fluorescent proteins[END_REF], in addition to blinking [START_REF] Dickson | On/off blinking and switching behaviour of single molecules of green fluorescent protein[END_REF],

and photobleaching [START_REF] White | Photobleaching GFP reveals protein dynamics inside live cells[END_REF]. These low-yield processes have mostly been perceived as nuisances, until the discovery of fluorescent proteins from Anthozoa species completely changed our view. Starting with Kaede in Trachyphyllia geoffroyi and EosFP in Lobophyllia hemprichii, well-behaved green-to-red photoconvertible FPs soon suggested a huge potential for dynamical tracking experiments and super-resolution localization microscopy, and were rapidly developed into a whole palette of highly performing variants. Likewise, after the discovery of the reversibly switchable asFP595 in Anemonia sulcata, the engineering of monomeric Dronpa from Echinophyllia sp. revolutionized the field, and was followed by the release of many variants opening up a continuously growing panel of applications, from biotechnology to optogenetics. In the meantime, GFP itself was turned into a highly efficient photoactivatable protein named PA-GFP and different hues followed, adequate for e.g. pulse-chase microscopy approaches. PTFPs developed in the last two years are summarized in Table 1. The present paper mainly focuses on future challenges in the field of PTFPs. For a comprehensive view on PTFP's mechanisms, engineering and applications, the reader is directed to the many exhaustive reviews published recently [START_REF] Dedecker | Fluorescent proteins: shine on, you crazy diamond[END_REF][START_REF] Nienhaus | Fluorescent proteins for live-cell imaging with superresolution[END_REF][8][START_REF] Sengupta | Superresolution imaging of biological systems using photoactivated localization microscopy[END_REF][START_REF] Bourgeois | Reversible photoswitching in fluorescent proteins: a mechanistic view[END_REF][START_REF] Bourgeois | Photoactivated structural dynamics of fluorescent proteins[END_REF][START_REF] Adam | Phototransformable fluorescent proteins: which one for which application?[END_REF]. We start by Then, based on three fascinating examples from recent literature, we highlight important flaws that PTFPs still face today. We list a series of mechanistic questions still to be investigated, and we propose perspectives for further developments of PTFPs.

PTFPs classes and mechanisms

In PTFPs, three main classes are distinguished. Photoactivatable fluorescent proteins (PAFPs) undergo non-reversible light-induced activation from a non-fluorescent to a fluorescent state; photoconvertible FPs (PCFPs) exhibit non-reversible conversion between two fluorescent states with distinct emission colors; and reversibly switchable FPs (RSFPs) can be photoswitched back and forth between a fluorescent on-state and a non-fluorescent off-state. In PAFPs and PCFPs, the phototransformations involve covalent modifications of the FP whereas in RSFPs only conformational rearrangements of the chromophore and its environment take place. The basic mechanisms involved are illustrated in figure 1. It should be noted that PCFPs and RSFPs of anthozoan origin often share remarkably high sequence identity and structural similarity. This allowed the development of PTFPs combining both photoconversion and photoswitching properties [START_REF] Adam | Rational design of photoconvertible and biphotochromic fluorescent proteins for advanced microscopy applications[END_REF] and the re-engineering of PCFPs into RSFPs [START_REF] Chang | A unique series of reversibly switchable fluorescent proteins with beneficial properties for various applications[END_REF] or vice versa [START_REF] Moeyaert | Green-to-red photoconvertible Dronpa mutant for multimodal super-resolution fluorescence microscopy[END_REF].

PAFPs: photoactivatable fluorescent proteins

PATagRFP [START_REF] Subach | Bright monomeric photoactivatable red fluorescent protein for two-color superresolution sptPALM of live cells[END_REF] and PAmKate [START_REF] Gunewardene | Superresolution imaging of multiple fluorescent proteins with highly overlapping emission spectra in living cells[END_REF] are the latest introduced PAFPs, with a red (595 nm) and far red (628 nm) fluorescence emission in their activated state, respectively. Despite a relatively low brightness, these two proteins could successfully be used in multicolor localization microscopy experiments [START_REF] Subach | Bright monomeric photoactivatable red fluorescent protein for two-color superresolution sptPALM of live cells[END_REF][START_REF] Gunewardene | Superresolution imaging of multiple fluorescent proteins with highly overlapping emission spectra in living cells[END_REF]. Whereas the photoactivation mechanisms of PA-GFP and PAmCherry are relatively well-established, involving decarboxylation of the fully conserved Glu222 through photo-Kolbe reactions, those of PATagRFP and PAmKate remain to be deciphered. In PATagRFP, the presence of oxygen is required to promote chromophore oxidation, like in PAmCherry. The reaction involves uncharacterized intermediate states and the consecutive absorption of twonear-UV photons (CTPA, e.g. 405 nm) [START_REF] Subach | Bright monomeric photoactivatable red fluorescent protein for two-color superresolution sptPALM of live cells[END_REF], not to be confused with the simultaneous absorption of two photons, commonly referred as TPA. In Phototransformable fluorescent proteins 19/05/2014 fact, Glu222 decarboxylation in PA-GFP is also mainly a CTPA process [START_REF] Langhojer | Ultrafast photoconversion of the green fluorescent protein studied by accumulative femtosecond spectroscopy[END_REF][START_REF] Ding | Reaction mechanism of photoinduced decarboxylation of the photoactivatable green fluorescent protein: an ONIOM(QM:MM) study[END_REF], raising the question how weak 405-nm light still activates PA-GFP. Interestingly, Glu222 decarboxylation can cause photobleaching in some anthozoan PCFPs or RSFPs [START_REF] Duan | Structural evidence for a two-regime photobleaching mechanism in a reversibly switchable fluorescent protein[END_REF], instead of photoactivation, which suggests the existence of two parallel photoactivation mechanisms.

PCFPs: photoconvertible fluorescent proteins

Whereas well-known green-to-red PCFPs emit below 600 nm in their photoconverted state, the recently introduced PSmOrange [21] and PSmOrange2 [22] shift their emissions from orange to the dark red region (660 nm) upon illumination at 488 nm. The photoconversion mechanisms of these two proteins remain to be precisely established but appear to involve CTPA, like PATagRFP, as well as the presence of oxidizing agents in the nanoenvironment. This is in stark contrast to the mechanism of Kaede-or Eos-like PCFPs, in which backbone breakage and elongation of the chromophoric -system results from absorption of a single UV-violet photon and can be prevented by addition of electron acceptors in the medium [23]. The engineering of a least-evolved ancestral PCFP [24] and ultrafast spectroscopic investigations [25,26] contributed to clarify the mechanism by which green-to-red PCFPs photoconvert. Evidence is growing that a histidine-containing and protonated chromophore embedded in a "typical" anthozoan-FP chromophore pocket does not guarantee efficient photoconversion and that the local charge network [24] as well as global conformational dynamics e.g. due to the oligomeric structure of PCFPs [START_REF] Moeyaert | Green-to-red photoconvertible Dronpa mutant for multimodal super-resolution fluorescence microscopy[END_REF] play key roles. In Dendra2, the mechanism by which the anionic chromophore may also promote photoconversion remains unclear. Of major concern is the observation that photoconversion in green-to-red PCFPs is always incomplete (meaning that only a fraction of PCFPs in a sample is able to achieve photoconversion) [27], complicating quantitative molecular counting using PALM (see [START_REF] Sengupta | Superresolution imaging of biological systems using photoactivated localization microscopy[END_REF] and Figure 2b). The mechanistic reason, and a possible cure, for such incomplete photoconversion are still lacking.

RSFPs: reversibly switchable (or photochromic) fluorescent proteins

RSFPs offer the widest range of applications [START_REF] Bourgeois | Reversible photoswitching in fluorescent proteins: a mechanistic view[END_REF][START_REF] Adam | Phototransformable fluorescent proteins: which one for which application?[END_REF], and therefore many efforts have been devoted recently to extend their panel [START_REF] Adam | Rational design of photoconvertible and biphotochromic fluorescent proteins for advanced microscopy applications[END_REF][START_REF] Chang | A unique series of reversibly switchable fluorescent proteins with beneficial properties for various applications[END_REF][START_REF] Moeyaert | Green-to-red photoconvertible Dronpa mutant for multimodal super-resolution fluorescence microscopy[END_REF]22,[28][START_REF] Jablonski | Optically modulatable blue fluorescent proteins[END_REF][START_REF] Lavoie-Cardinal | Two-color RESOLFT nanoscopy with green and red fluorescent photochromic proteins[END_REF][START_REF] Zhang | Rational design of true monomeric and bright photoactivatable fluorescent proteins[END_REF] and tackle their mechanisms Phototransformable fluorescent proteins 19/05/2014 [START_REF] Moeyaert | Green-to-red photoconvertible Dronpa mutant for multimodal super-resolution fluorescence microscopy[END_REF][START_REF] Duan | Structural evidence for a two-regime photobleaching mechanism in a reversibly switchable fluorescent protein[END_REF][START_REF] Faro | Low-temperature chromophore isomerization reveals the photoswitching mechanism of the fluorescent protein Padron[END_REF][START_REF] Fron | Excited state dynamics of photoswitchable fluorescent protein Padron[END_REF][START_REF] Gayda | Mechanistic insights into reversible photoactivation in proteins of the GFP family[END_REF][START_REF] Warren | Groundstate proton transfer in the photoswitching reactions of the fluorescent protein Dronpa[END_REF]. Photoswitching in RSFPs is generally based on an intrinsic property of theisolated chromophore: light-induced cis-trans isomerization. Therefore photoswitching tends to naturally occur to some extent in many FPs, and has been successfully expanded by engineering in both hydrozoan and anthozoan RSFPs. Depending on whether photon absorption at the peak excitation wavelength induces off-switching, on-switching, or has no switching effect, RSFPs are referred to as negative [START_REF] Ando | Regulated fast nucleocytoplasmic shuttling observed by reversible protein highlighting[END_REF], positive [START_REF] Andresen | Photoswitchable fluorescent proteins enable monochromatic multilabel imaging and dual color fluorescence nanoscopy[END_REF], or decoupled [START_REF] Brakemann | A reversibly photoswitchable GFP-like protein with fluorescence excitation decoupled from switching[END_REF], respectively, each having their pros and cons. Recent findings concern the heavily debated mechanism by which chromophore isomerization couples to chromophore protonation in negative or positive anthozoan switchers. Several pieces of evidence from ultrafast IR and UV-vis spectroscopy now suggest that (de)protonation of the chromophore in Dronpa [START_REF] Warren | Groundstate proton transfer in the photoswitching reactions of the fluorescent protein Dronpa[END_REF] or Padron [START_REF] Fron | Excited state dynamics of photoswitchable fluorescent protein Padron[END_REF] is a ground state process that follows isomerization, although other authors disagree [START_REF] Gayda | Mechanistic insights into reversible photoactivation in proteins of the GFP family[END_REF]. Another interesting finding is that negative switchers such as Padron are capable of efficient photoswitching at cryogenic temperatures [START_REF] Faro | Low-temperature chromophore isomerization reveals the photoswitching mechanism of the fluorescent protein Padron[END_REF], potentially opening up nanoscopy applications at such low temperatures. Recent engineering efforts have also aimed at increasing the switching speed and fatigue resistance (i.e. the number of achievable photo cycles before photobleaching) of RSFPs of use for e.g. RESOLFT applications [28,[START_REF] Testa | Nanoscopy of living brain slices with low light levels[END_REF] (see below and Figure 2c). Blue and infrared RSFPs have been developed that, despite their low brightness, offer exciting perspectives for extracting weak signals by demodulation [START_REF] Jablonski | Optically modulatable blue fluorescent proteins[END_REF] or difference imaging (see [START_REF] Piatkevich | Far-red light photoactivatable nearinfrared fluorescent proteins engineered from a bacterial phytochrome[END_REF] and Figure 2a) in conditions of high autofluorescence.

PTFPs applications

PTFPs are presently used in a very wide panel of applications [START_REF] Dedecker | Fluorescent proteins: shine on, you crazy diamond[END_REF][START_REF] Nienhaus | Fluorescent proteins for live-cell imaging with superresolution[END_REF][8][START_REF] Sengupta | Superresolution imaging of biological systems using photoactivated localization microscopy[END_REF][START_REF] Bourgeois | Reversible photoswitching in fluorescent proteins: a mechanistic view[END_REF][START_REF] Bourgeois | Photoactivated structural dynamics of fluorescent proteins[END_REF][START_REF] Adam | Phototransformable fluorescent proteins: which one for which application?[END_REF] that cannot be exhaustively reviewed here. One recent evolution is that attention is now often paid to optimizing PTFPs for several applications instead of only one, allowing to obtain complementary results with a single construct [START_REF] Moeyaert | Green-to-red photoconvertible Dronpa mutant for multimodal super-resolution fluorescence microscopy[END_REF][START_REF] Mcevoy | mMaple: a photoconvertible fluorescent protein for use in multiple imaging modalities[END_REF][START_REF] Jensen | Coordinate-targeted and coordinate-stochastic super-resolution microscopy with the reversibly switchable fluorescent protein Dreiklang[END_REF]. In this regard, bi-photochromic PTFPs such as NijiFP or Dendra2-M159A [START_REF] Adam | Rational design of photoconvertible and biphotochromic fluorescent proteins for advanced microscopy applications[END_REF] or three-way highlighters like pcDronpa2 [START_REF] Moeyaert | Green-to-red photoconvertible Dronpa mutant for multimodal super-resolution fluorescence microscopy[END_REF] are versatile members that may offer novel applications in the future.

In the following, we take advantage of three outstanding papers to highlight three major challenges that PTFPs' research will face in the next years.

Phototransformable fluorescent proteins 19/05/2014

Expanding the PTFPs toolbox with infrared-emitting members

Far-red-shifted variants are a necessary ingredient in deep-tissue or live-animal imaging. In a recent tour-de-force, Piatkevitch et al. [START_REF] Piatkevich | Far-red light photoactivatable nearinfrared fluorescent proteins engineered from a bacterial phytochrome[END_REF] developed an infrared-RSFP by exploiting the photocycle of phytochromes between red (Pr) and far-red (Pfr) states. The photosensory core domain of a bacterial phytochrome was engineered to provide PAiRFP1 and PAiRFP2, which can be reversibly switched by 660-nm light into a Pfr-like state emitting fluorescence at ~718 nm. Despite their low fluorescence quantum yield and suboptimal contrast ratio (fluorescence in the off state amounts to ~20% of that in the on-state), the two proteins facilitate deep-tissue imaging: the difference between images recorded in the on and off state of the markers can be computed to highlight e.g. a labeled tumor region (Figure 2a). In general, far-red and infrared FPs all suffer from a low fluorescence quantum yield (~5% for PAiRFP1/2), possibly due to the many degrees of freedom in elongated chromophores, promoting a multitude of non-radiative de-excitation pathways. Thus far, iPTFPs are therefore inappropriate for single molecule detection and a challenge for the future will be to engineer iPTFPs of high-brightness suitable for localization microscopy.

Mastering Dendra2 photophysics to monitor transient clustering of RNA polymerase in live cells

Localization microscopy has recently turned into a quantitative method to count macromolecules within cells, assess their stoichiometry or monitor their clustering pattern.

The work by Cisse et al [START_REF] Cisse | Real-time dynamics of RNA polymerase II clustering in live human cells[END_REF] illustrates this trend, introducing time-correlated PALM (CTPALM) to dynamically measure the clustering of RNA polymerase II (Pol II) in the nuclei of live human cells. By analyzing the temporal sequence of single-molecule detections in individual clusters, it was shown that "nuclear transcription factories" made of Pol II clusters continuously assemble and disassemble (Figure 2b). To confidently interpret the results, Cisse et al, however, had to pay critical attention to the complex photophysics of the employed PCFP marker, Dendra2. Like many other PCFPs, Dendra2 stochastically switches to long-lived dark states once photoconverted, which confuses quantitative studies because each molecule may be counted more than once. A number of methods have been proposed to tackle this difficulty, but they are all statistical by nature and thus remain imperfect [START_REF] Sengupta | Superresolution imaging of biological systems using photoactivated localization microscopy[END_REF].

Phototransformable fluorescent proteins 19/05/2014

There is yet no clear understanding of the exact mechanism giving rise to this slow blinking, and the nano-environmental sensitivity of the process remains to be assessed. A combination of structural [START_REF] Adam | Structural characterization of IrisFP, an optical highlighter undergoing multiple photo-induced transformations[END_REF][START_REF] Roy | The nature of transient dark states in a photoactivatable fluorescent protein[END_REF] and single-molecule [START_REF] Lee | Counting single photoactivatable fluorescent molecules by photoactivated localization microscopy (PALM)[END_REF][START_REF] Mckinney | A bright and photostable photoconvertible fluorescent protein[END_REF] data on mEos2, Dendra2 and IrisFP suggests that a blinking mechanism in anthozoan PTFPs could involve a transient protonation of carbon C  of the chromophore methylene bridge via the nearby Arg66 (Figure 3a). Alternatively, the long dark states could relate to a residual propensity to cistrans chromophore isomerization. Another difficulty in Cisse et al is that the exact numbers of Pol II molecules forming the clusters could not be extracted because of the suboptimal photoconversion efficiency of Dendra2: a number of labeled Pol II molecules never get photoconverted and are thus not counted. Elegant methods have been proposed recently to evaluate the problem in various PCFPs [27] and to correct for it [START_REF] Puchner | Counting molecules in single organelles with superresolution microscopy allows tracking of the endosome maturation trajectory[END_REF], but the underlying photophysics remains mysterious.

Thus, challenges for the future will be to better understand the complex blinking and photoconversion behavior of PCFPs and engineer low-blinking and fully photoconvertible variants.

Video-rate super-resolution microscopy with RSFPs

The concomitant development of sophisticated optical setups and dedicated RSFPs has considerably advanced the nanoscopy approach named RESOLFT [28, [START_REF] Testa | Nanoscopy of living brain slices with low light levels[END_REF][START_REF] Chmyrov | Nanoscopy with more than 100,000 'doughnuts[END_REF]. By employing RSFPs with long on-and off-state lifetimes, RESOLFT requires considerably less light than STED nanoscopy to break the diffraction barrier, but at the expense of a reduced timeresolution. However, employing RSFPs with high switching speed such as Dronpa-M159T [START_REF] Testa | Nanoscopy of living brain slices with low light levels[END_REF] or rsEGFP2 [28] allowed relatively fast dynamic RESOLFT imaging. Chmyrov et al [START_REF] Chmyrov | Nanoscopy with more than 100,000 'doughnuts[END_REF] demonstrated that video-rate RESOLFT nanoscopy could be achieved on very large field-ofviews by designing a highly parallelized setup based on orthogonal and incoherently crossed standing light waves. The spectacular images (Figure 2c) were obtained with rsEGFP(N205S), a slow switching variant of rsEGFP that, by emitting about twice the number of photons per cycle, allowed obtaining images of excellent signal-to-noise ratio. Slow-switching variants such as rsEGFP(N205S) deliver high quality images but limit the achievable acquisition rate, which in the present case was more than compensated by the parallelized optical setup.

Noteworthy, the light intensity and the cellular environment influence the switching Phototransformable fluorescent proteins 19/05/2014 properties of RSFPs [28] and many other photophysical parameters (e.g. brightness, expression level, maturation rate, contrast ratio) determine the achievable image quality.

Another critical aspect in RESOLFT is that the resolution enhancement is limited by the fatigue resistance of the RSFP, calling for more photostable RSFPs (and PTFPs in general).

Progress in this direction has been achieved by directed evolution [28] and by recent investigations on IrisFP revealing that that two completely different photobleaching mechanisms occur in anthozoan PTFPs [START_REF] Duan | Structural evidence for a two-regime photobleaching mechanism in a reversibly switchable fluorescent protein[END_REF]. At light levels typical of standard widefield microscopy (<< 100 W/cm²), IrisFP photobleaching involves an oxygen-dependent mechanism, whereas at light levels employed in PALM microscopy (>> 100 W/cm²) an oxygen-independent CTPA process dominates (Figure 3b,c). It remains unknown whether similar scenarios occur in hydrozoan PTFPs such as rsEGFP or at higher light levels typical of RESOLFT nanoscopy.

Overall, challenges for the future will be to rationally design high-contrast-ratio, fastswitching, high-brightness and fatigue-resistant RSFPs.

Further mechanistic questions

Fluorescent molecules are highly sensitive to their environment. While the role of the environment surrounding organic dyes has drawn considerable research efforts, for example to develop dSTORM nanoscopy [START_REF] Van De Linde | How to switch a fluorophore: from undesired blinking to controlled photoswitching[END_REF], its importance in PTFPs has been underestimated. Yet, the -barrel embedding the chromophore in FPs is generally flexible and permeable. Oxygen [START_REF] Subach | Bright monomeric photoactivatable red fluorescent protein for two-color superresolution sptPALM of live cells[END_REF]21,[START_REF] Regmi | Exploring the diffusion of molecular oxygen in the red fluorescent protein mCherry using explicit oxygen molecular dynamics simulations[END_REF] and small buffer components such as ethylene glycol [START_REF] Von Stetten | Alteration of fluorescent protein spectroscopic properties upon cryoprotection[END_REF] can reach the chromophore, while vitamins in the medium may accelerate photobleaching [START_REF] Bogdanov | Anti-fading media for live cell GFP imaging[END_REF]. There is more and more evidence that the efficiency of phototransformations are influenced by the cellular and/or redox microenvironment, as shown for the oxidative redding of EGFP [23,[START_REF] Bogdanov | Anti-fading media for live cell GFP imaging[END_REF], the photoconversion of mEos2 [START_REF] Izeddin | Superresolution dynamic imaging of dendritic spines using a low-affinity photoconvertible actin probe[END_REF], or the photoswitching of rsEGFP variants [28]. However, the precise proton and electron pathways, oxygen routes or role of cavities within PTFP structures remain to be determined. Influences of the solvent on the blinking and bleaching behaviors of PTFPs have also been observed, e.g. presence of redox active molecules such as MEA [START_REF] Endesfelder | Chemically induced photoswitching of fluorescent probes--a general concept for super-resolution microscopy[END_REF]. In all these cases, the barrel could act as relaying networks via H-bonds or redox

Perspectives for future PTFPs

Fluorescence appears much more widespread in oceans than previously thought, as even vertebrates such as fishes have been found to emit fluorescence [START_REF] Sparks | The covert world of fish biofluorescence: a phylogenetically widespread and phenotypically variable phenomenon[END_REF]. Putative FPs of these organisms probably undergo entirely different fluorescence mechanisms than those involved in GFP-like types, thus offering the opportunity for considerable enlargement of the FP toolbox. A recent example is UnaG, a protein of about half the size of GFP, discovered in a freshwater eel and that fluoresces green upon reversible binding of bilirubin [START_REF] Kumagai | A bilirubin-inducible fluorescent protein from eel muscle[END_REF]. Another alternative to conventional FPs resides in the increasing use of Light, Oxygen, or Voltagesensing (LOV) flavoprotein domains [START_REF] Wingen | The photophysics of LOV-based fluorescent proteins -new tools for cell biology[END_REF] whose covalently linked flavin chromophore does not require oxygen to maturate. Amongst other advantages, their small size allows the exploration of tight cellular compartments as recently demonstrated for bacterial periplasm [START_REF] Zhang | Exploring the size limit of protein diffusion through the periplasm in cyanobacterium Anabaena sp. PCC 7120 using the 13 kDa iLOV fluorescent protein[END_REF]. Engineering these new types of FPs so that they become phototransformable represents a future quest.

Yet, existing PTFPs have still much to offer and will continue to be refined by genetic engineering. Underappreciated improvements such as codon optimizations or adaptations of C and N termini are possible solution to rescue non-functional genetic fusions and to explore "FP-hostile" (e.g. acidic or oxidative) organelles or organisms.

PTFPs also need to see their color palette expanded. The incorporation of non-natural amino acids is a promising route as they can form novel chromophores [START_REF] Liu | Significant expansion of the fluorescent protein chromophore through the genetic incorporation of a metal-chelating unnatural amino acid[END_REF][START_REF] Groff | A new strategy to photoactivate green fluorescent protein[END_REF]. Plotting the brightness of PTFPs versus their emission color (Figure 4), it appears that, despite recent efforts [START_REF] Jablonski | Optically modulatable blue fluorescent proteins[END_REF][START_REF] Piatkevich | Far-red light photoactivatable nearinfrared fluorescent proteins engineered from a bacterial phytochrome[END_REF], most PTFPs concentrate nowadays in the green and orange range of emission, leaving the violet/blue and red/far red regions weakly populated. Even more Phototransformable fluorescent proteins 19/05/2014 strikingly, the few PTFPs engineered from yellow FPs such as EYQ1 [START_REF] Abbruzzetti | Photoswitching of E222Q GFP mutants: "concerted" mechanism of chromophore isomerization and protonation[END_REF] or Dreiklang [START_REF] Brakemann | A reversibly photoswitchable GFP-like protein with fluorescence excitation decoupled from switching[END_REF] ended up with green variants and it appears that, unlike conventional FPs, yellowish PTFPs emitting between 530 and 560 nm are totally missing. This absence is particularly noteworthy since this is precisely the wavelength range where the brightness is expected to be the highest [START_REF] Dedecker | Fluorescent proteins: shine on, you crazy diamond[END_REF] so that the engineering of bright yellow PTFPs remains a challenge.

In conclusion, unfolding the full potential of PTFPs will continue to keep developers busy for a while -provided continued funding is made available-! the type of damage inflicted on a PTFP by visible light is dependent on its intensity: at low flux an oxygen-dependent mechanism prevails, whereas higher flux favors reductive chromophore destruction.

21. Subach OM, Patterson GH, Ting LM, Wang Y, Condeelis JS, Verkhusha VV: A photoswitchable orange-to-far-red fluorescent protein, PSmOrange. Nat Methods 2011, 8:771-777.

• 22. Subach OM, Entenberg D, Condeelis JS, Verkhusha VV: A FRET-facilitated photoswitching using an orange fluorescent protein with the fast photoconversion kinetics. J Am Chem Soc 2012, 134:14789-14799.

Optimizing absorption wavelength and photoconversion rate of the orange-to-deep-red switcher PSmOrange, the authors succeed in triggering the photoconversion by FRET from a green emitting FP, thus creating a "memory" of a transient interaction. 13 mutations were shown to be necessary and sufficient to evolve GFP into a hydrozoan PCFP. Structural and biochemical studies convincingly suggest a green-to-red photoconversion mechanism in which Glu222 abstracts a proton from His65 in the excited state and transfers it to Phe64 via Gln42 to promote bond cleavage and chromophore extension. The quadrupolar network consisting of Glu222, His203, Glu148 and Arg69, as well as the residue Gln42 are proposed to play an essential role in the process. An interesting example of in cellulo evaluation of PTFP's photophysics at the single molecule level. A nanotemplate approach allowed to precisely evaluate the photoconversion and photoactivation efficiencies of a variety of PCFPs and PAFPs. A maximum of 60% photoconversion efficiency was demonstrated for mEos2.

• 28. Grotjohann T, Testa I, Reuss M, Brakemann T, Eggeling C, Hell SW, Jakobs S: rsEGFP2 enables fast RESOLFT nanoscopy of living cells. eLife 2012, 1:e00248.

In a mutagenesis effort, the authors obtained a double mutant of their EGFP-based reversibly switchable fluorescent protein (rsEGFP) whose photoswitching efficiency is improved. The resulting variant called rsEGFP2 makes it possible to accelerate the RESOLFT acquisition times up to 250 times. Furthermore, with a similar brightness as compared to its parent, rsEGFP2 is two times more Important features are depicted in red.

Click here to download high resolution image

  Phototransformable fluorescent proteins

  Phototransformable fluorescent proteins

  23. Saha R, Verma PK, Rakshit S, Saha S, Mayor S, Pal SK: Light driven ultrafast electron transfer in oxidative redding of green fluorescent proteins. Sci Rep 2013, 3:1580. •• 24. Kim H, Grunkemeyer TJ, Modi C, Chen L, Fromme R, Matz MV, Wachter RM: Acid-base catalysis and crystal structures of a least evolved ancestral GFP-like protein undergoing green-to-red photoconversion. Biochemistry 2013, 52:8048-8059.

  25. Fron E, Van der Auweraer M, Moeyaert B, Michiels J, Mizuno H, Hofkens J, Adam V: Revealing the excited-state dynamics of the fluorescent protein Dendra2. J Phys Chem B 2013, 117:2300-2313. 26. Fron E, Sliwa M, Adam V, Michiels J, Rocha S, Dedecker P, Hofkens J, Mizuno H: Excited state dynamics of the photoconvertible fluorescent protein Kaede revealed by ultrafast spectroscopy. Photochem Photobiol Sci 2013. • 27. Durisic N, Laparra-Cuervo L, Sandoval-Alvarez A, Borbely JS, Lakadamyali M: Single-molecule evaluation of fluorescent protein photoactivation efficiency using an in vivo nanotemplate. Nat Methods 2014, 11:156-162.

Fig. 1 :

 1 Phototransformable fluorescent proteins

Fig. 2 :

 2 Fig. 2: Using PTFPs for deep-tissue imaging, counting macromolecules in dense clusters and developing video-rate nanoscopy.

Fig. 3 :

 3 Fig. 3: Phototransformation mechanisms associated with blinking and bleaching in IrisFP. (a) Blinking involves a thermally-reversible photoinduced proton exchange between Arg66 and the methylene bridge of the chromophore. (b) Bleaching under weak-illumination involves an oxygen-dependent mechanism that results in sulfoxidation of the Met159 and trapping of the chromophore in a protonated/non-fluorescent form. (c) Bleaching under strong-illumination conditions results in the decarboxylation of Glu212, conformational

Fig. 4 :

 4 Fig. 4: Brightness distribution of conventional FPs and PTFPs as a function of their emission colors. (a) Conventional FPs and (b) PTFPs are represented by points and labels that are colored to the approximate appearance to the naked eye. The dashed bell-shaped curves highlight the general distributions of brightness. This figure is an extended version of a figure inspired by [1]. Note that a few labels are omitted for sake of readability and that PTFPs are represented in their activated form only. The absence of PTFPs emitting in the 530-560-nm window is apparent. The histograms (insets) represent the distribution of FPs and PTFPs as a function of their emission wavelengths (bin-width = 15 nm).

Figure 2 Click here to download high resolution image Figure 3 Click here to download high resolution image Figure 4

 234 Figure 2 Click here to download high resolution image

Table 1 -Properties of important PTFPs developed during the last two years.

 1 The table summarizes the photophysical properties of PTFPs prior (PRE) and after (POST) their phototransformation. It is noteworthy that in the last two years, to the authors' knowledge, no PAFPs have been developed. a Abbreviations:  max ex/em, maximum of excitation/emission spectrum; , molar extinction coefficient;  fluo , fluorescence quantum yield. b Brightness is the product of fluorescence quantum yield and molar extinction coefficient expressed in % of the EGFP brightness. c wavelengths required for irreversible (PCFPs) or reversible (RSFPs) transitions. M, monomer; D, dimer; T, tetramer; NA, not applicable; ND, not determined. The sign of the photoswitching in RSFPs is depicted by (-) for negative and (+) for positive switching

	Protein (oligomerization)	Parent protein [wild-type]	Source organism	Chromo-phore	max ex/em (nm)	a  (mM -1 .cm -1 ) a	fluo	a	Brightness	b	pKa		Actinic light (nm) c	Ref.
	PHOTOCONVERTIBLE FLUORESCENT PROTEINS (PCFPs)	PRE	POST		PRE	POST	PRE	POST	PRE	POST	PRE	POST
	mEos3.1 (M)	mEos2 [EosFP]	L. hemprichii	HYG	505/513 570/580	88.4	33.5	0.83	0.62	218%	62%	5.2	6.0		405	[31]
	mEos3.2 (M)	mEos2 [EosFP]	L.hemprichii	HYG	507/516 572/580	63.4	32.2	0.84	0.55	159%	53%	5.4	5.8		405	[31]
	mMaple (M)	mClavGR2	Clavularia sp.	HYG	489/505 566/583	15	30	0.74	0.56	33%	50%	8.2	7.3		405	[41]
	pcDronpa (T)	Dronpa [22G]	Echinophyllia sp. SC22	HYG	505/517 569/581	115	75	0.85	0.68	291%	190%	5.5	6.3		405	[15]
	pcDronpa2 (T)	Dronpa [22G]	Echinophyllia sp. SC22	HYG	504/515 569/583	100	105	0.83	0.68	248%	213%	5.8	6.1		405	[15]
	PSmOrange2 (M)	mOrange [DsRed]	Discosoma sp.	TYG	546/561 619/651	51	18.9	0.61	0.38	95%	23%	6.6	5.4		488	[22]
	REVERSIBLY SWITCHABLE FLUORESCENT PROTEINS (RSFPs)	PRE	POST		PRE	POST	PRE	POST	PRE	POST	PRE	POST	on-off	off-on
	(-) modBFP (M)	mKalama1 [GFP]	A. victoria	SYG	390/455	NA		27	NA	0.33	NA	26%	NA	5.5	ND	405	514	[29]
	(-) mIrisGFP (M)	IrisFP [EosFP]	L. hemprichii	HYG	488/516	NA		47	18	0.63	NA	89%	NA	5.3	>10	473	405	[34]
	(-) mGeos-M (M)	mEos2 [EosFP]	L. hemprichii	MYG	503/514	NA		51.6	NA	0.85	NA	131%	NA	4.5-5.0	ND	488	405	[14]
	(-) rsEGFP2 (M)	EGFP [GFP]	A. victoria	AYG	478/503	NA		61	NA	0.30	NA	~60%	NA	ND	ND	488	405	[28]
	(-) rsCherryRev 1.4 (M)	rsCherryRev [DsRed]	Discosoma sp.	MYG	572/609	NA		ND	NA	ND	NA	ND	NA	ND	5.5	592	430	[30]
	(+) PAiRFP1 (D)	AtPCD [AtBphP2]	A. tumefaciens C58	billiverdin	659/703 690/717	48.7	67.1	NA	0.048	9.6%	ND	4.6	5.2	-	660/750 [40]
	(+) PAiRFP2 (D)	AtPCD [AtBphP2]	A. tumefaciens C58	billiverdin	657/708 692/719	39.5	63.6	NA	0.047	8.9%	ND	4.7	5.4	-	660/750 [40]

Note:

Acknowledgments

The authors acknowledge V. Verkhusha, I. Izeddin and A. Chmyrov for providing raw images to adapt figure 2. Institutional grants from the CNRS, CEA and UJF and financial support by the ANR (ANR-2011-BSV5-012-01 NOBLEACH) are acknowledged.


Yves Bertot
email: yves.bertot@inria.fr

Formal computation Fixed precision patterns for the formal verification of mathematical constant approximations

We describe two approaches for the computation of mathematical constant approximations inside interactive theorem provers. These two approaches share the same basis of fixed point computation and differ only in the way the proofs of correctness of the approximations are described. The first approach performs interval computations, while the second approach relies on bounding errors, for example with the help of derivatives. As an illustration, we show how to describe good approximations of the logarithm function and we compute π to a precision of a million decimals inside the proof system, with a guarantee that all digits up to the millionth decimal are correct. All these experiments are performed with the Coq system, but most of the steps should apply to any interactive theorem provers.

Introduction

Modern higher-order logic proof systems are usually well-suited to describe real numbers and to reason about computations based on this type of number. However, when it comes to comparing numbers, it is often useful to have approximations that make it easy to show how the comparison should be solved, with only exceptions occurring when the comparison is tight, where pure mathematical reasoning remains the surest solution.

A principled approach to this question is to first study a mathematical algorithm that approximates the intended real computation, and then to study how this mathematical algorithm is refined taking into account the fact that most elementary operations are not performed exactly, but only approximately. Thus, the same mathematical object can be represented by three values: (i) the exact real number x (often the limit of an infinite sequence of other real numbers xn), (ii) a real number approximating x expressed using only elementary operations (often one of the elements of the infinite sequence, say xp for some fixed p), (iii) an approximated version the real value, as described in a number system that only covers a denumerable subset of the real numbers (an approximation of x, computed with rounded elementary operations).

For instance, we may consider the constant π. Among the three values mentioned in the previous paragraph, π itself plays the [Copyright notice will appear here once 'preprint' option is removed.] role (i). This constant may be computed using Machin's formula π = 4×(4 atan( 15 )-atan( 1 239 )). Each of the arctangent function calls (the function noted atan) can then be approximated as the limit described by the following definition:

atan(x) = lim n→∞ n i=0 (-1) i x 2i+1
2i + 1

Putting everything together, we know that

4 × (4 × ( 1 5 - 1 3 × 5 3 ) - 1 239
)

is an under approximation of π. This value plays the role (ii). When computing a decimal representation of this number, we can choose to use decimal representations for the various terms in the sum, like 1 3 × 5 3 . But for this term, no finite decimal representation is exact, so that the final value that we compute when using 5 decimal places, 3.14059 is again an under approximation. This value plays the role (iii).

Thus, there are two approximations being performed in the process, each of them introduces an approximation error and we want to prove properties of these errors. In this paper, we will focus mostly on the second part: once we know a mathematical process, using only elementary operations (addition, subtraction, division, multiplication, and square root), how can we represent this process using concrete computations in an interactive theorem prover, so that we obtain an easy to use approximation of this constant. All our techniques will rely on integer computations and assume that we have a library to perform these computations in a formally verified way. In a first section, we will show the approach we advocate to perform high precision computation, which practically boils down to fixed point computation.

We then will describe two approaches. In the first approach, we will reproduce interval analysis at the level of each elementary operation. Each value will be known through a formally verified upper bound and a formally verified lower bound, and we will use bounds on inputs to compute bounds on outputs. In the second approach, we will only assume that each input is known within a given error and we will study how this error is modified by successive operations. In particular, we will see that we can prove tighter bounds with the second approach than with the first one, because it makes it possible to avoid the weakness of interval analysis known as the dependency or decorrelation problem.

Related work

Similar questions have been studied in a variety of proof systems over the last decade. A notable publication concerning the PVS system, by Daumas, Lester, and Muñoz [START_REF] Daumas | Verified real number calculations: A library for interval arithmetic[END_REF] completely describes interval arithmetics for most of the mathematical functions. These researchers prefered to use rational numbers to describe the bound of intervals. We also experimented with this approach, one advantage is that multiplication and division are exact. On the other hand, numerators and denominators of fractions tend to get very big. To keep them small, greatest common divisor computations need to be added, and this is costly.

Melquiond also worked on interval approaches, with experiments in the PVS system [START_REF] Daumas | Guaranteed Proofs Using Interval Arithmetic[END_REF] (with Daumas and Muñoz) and the Coq system [START_REF] Melquiond | Floating-point arithmetic in the Coq system[END_REF]. An advantage of this work is that it systematically uses interval splitting to reduce the effect of decorrelation. For the sake of completeness, we can illustrate here how to compute the natural logarithm of 10 using Melquiond's tool. We first compute iterated square roots on 10, to obtain a number smaller than 2, we then use a series expansion of the logarithm function. To conclude we need a proof of correctness for that series expansion (but this is not the point of this paper). This example only provides an upper bound for ln 16 √ 10 as a rational number whose denominator is a power of 2, a lower bound can be computed in a similar way. This example shows that the first method described in this paper (where we also use interval computations) is practically already covered by Melquiond's interval tactic. The most obvious restriction in the interval tactic is that it only works with powers of 2 as denominators of bounds. The work we describe in this paper around the logarithm function is slightly more general, since we obtain approximations with an arbitrary denominator.

Real numbers in Coq have also been studied extensively in the CCoRN library, with a strong constructive philosophy. In the constructive approach, every real number actually describes an algorithm that can give more and more precision as required. Obviously, this approach makes it possible to compute mathematical constants at an arbitrary precision. However, constructive real numbers are cumbersome to use from a pure classical point of view, because the equality of real numbers is not decidable (for instance, this precludes the definition of piece-wise continuous functions). A nice extension of this work is provided by Kaliszyk and O'Connor [START_REF] Kaliszyk | Computing with Classical Real Numbers[END_REF], who show that efficient implementations of real numbers in their constructive setting can also be used to reason about real numbers in the classical setting, which is the context of our work. Unfortunately, we have not been able to re-use their work, because it was not maintained continuously.

The Flyspeck project, concerned with the optimal placement of spheres in three-dimensional space is another setting where com-putations of real numbers play a significant role. A big part of this project is the verification of a large collection of inequalities for multi-variate functions, including most polynomial expressions, arctangent, square roots and constants like π. Obviously, a tool to verifiy inequalities would also be able to provide bounds for mathematical constants. Solovyev and Hales [START_REF] Solovyev | Formal verification of nonlinear inequalities with taylor interval approximations[END_REF] developed a specific tool for this need, and we expect it to be usable for moderate precision requirements, but it is explicitly stated in Solovyev's thesis [START_REF] Solovyev | Formal Computations and Methods[END_REF] that the tool is not tuned for extremely high precision. This development is done in HOL-Light [START_REF] Harrison | The HOL Light theorem prover[END_REF], which takes a more minimalist approach with respect to arithmetic computations than Coq. In Coq the big integers are computed using binary integer arithmetic directly for 31 bit integers.

This paper also describes (if only partially) the formally proved computation of π to a precision of the order of 10 10 6

, inside the Coq theorem prover. Most modern proof systems contain a definition of π and a tool to compute it to a high precision, but rarely exceeding 10 100 . Usually, the technique relies on a Machin-like formula 1 The algorithm we use in this paper is based on arithmeticgeometric means and was probably described for the first time in [START_REF] Borwein | Pi and the AGM[END_REF]. There is another, better known, algorithm also based on arithmetic-geometric means, published simultaneously and independently by Brent [START_REF] Brent | Fast multiple-precision evaluation of elementary functions[END_REF] and Salamin [START_REF] Salamin | Computation of π Using Arithmetic-Geometric Mean[END_REF]. That other algorithm is the one used in the high-precision, high-assurance, library MPFR [START_REF] Zimmermann | Reliable computing with GNU MPFR[END_REF]. Our execution time is still several orders of magnitude lower than in MPFR.

Fixed point computation

If we want to perform fixed point computation in decimal notation, it means that all numbers have a decimal point and a fixed number of digits to the right of the decimal point. For instance, we may decide to perform all computations with 5-digit after the decimal point. Numbers will have the following form: 1.00000 (this represents 1), 1.23456, (a number between 1 and 2), -4.22567 (a number between -5 and -4).

When it comes to adding two numbers with five digits, we can forget about the decimal point. We just start by adding the rightmost digits, then the next to rightmost digits with the carry, and so on. At the end, we only need to check that we again obtain numbers where the decimal point is 5 places from the right. In fact, we might as well just use integers, but remember that each integer actually represents a fractional number. This number is just obtained by dividing by 10 k , where k is simply the number of digits on the right of the decimal point. In our running example, k is 5.

Thus, we use plain addition between integers, but each number n actually is used to represent another real number [[n]]. This introduces a function [[•]], actually defined by the following property:

[[n]] = n 10 k .
In what follows, we will call magnification ratio the number 10 k , and we will forget about its shape and we will write µ in the mathematical formulas. Actually, it does not really matter that the number µ is a power of some base, and the number k will not occur anymore in our reasoning (but in our running example, we only need to remember that µ = 10 5 ). We have the following definition for the brackets:

[[n]] = n µ and conversely n = [[n]] × µ.

Addition commutes nicely with brackets [[•]

]. To add two real numbers represented by integers, we can simply add the two integers and then place the decimal point. This is expressed by the followint property.

[[n]] + [[m]] = [[n + m]]

When remembering the meaning of the brackets [[•]], this is just the following mathematical equality:

n µ + m µ = n + m µ . For multiplication, n × m is too big to represent [[n]] × [[m]]
, by the order of magnitude of µ. This is illustrated by the following equality:

n × m = [[n]] × µ × [[m]] × µ. If [[n]] and [[m]] are close to 1, then [[n]]×[[m]
] should also be close to 1, and should thus be represented by an integer close to µ. However,

n × m is close to µ 2 . Moreover, [[n]] × [[m]] cannot usually be represented exactly.
For instance, with 5 digits after the decimal point, we can consider the two numbers 1.00001 and 1.00002 and multiply them together. The exact result is 1.0000300002 and can only be approximated if using numbers with 5 digits after the decimal point. One of the simplest solutions is to take the largest representable number that is smaller than the exact value. When considering positive values, this simply corresponds to truncating the extra digits.

This rounding down mechanism is simply implemented by using an integer division, where the divisor is µ. When the input is positive, we simply keep the quotient. When the input is negative we have to be careful and check the exact form of division provided for integers in the formal library. Sometimes, the division is designed to always return a non-negative remainder; sometimes the division is designed to return the same absolute value for the quotient, with a negative remainder if the dividend is negative. In the latter case and with a negative dividend, the quotient can be returned exactly only when the remainder is zero, in all other cases, the quotient minus one must be returned.

Of course, rounding towards zero is only one of the possible choices; we could alternatively choose to round towards minus infinity (always down, even for negative values) or towards plus infinity (always up). In the course of this paper, we actually have uses for each of these possibilities.

To summarize our treatment of multiplication, let's just introduce a new notation, • d ⊗ • for multiplication with rounding towards minus infinity. Mathematically, this can be represented as follows:

n d ⊗ m = n × m µ .
When it comes to division, the same kind of reasoning can be performed, if we just divide n by m and keep the quotient, we do not obtain a number that has the right magnitude to represent

[[n]] [[m]] .
To understand this, it is simpler to write the mathematical formula:

n m = [[n]] × µ [[m]] × µ .
The two multiplications by µ cancel out in the fraction, while we were aiming at obtaining an integer close to the number

[[n]] [[m]] × µ.
The solution is to multiply by µ, but this should be done before the division, to make sure that we are not multiplying the rounding error.

For instance, when we consider the division of 1.00000 by 3.00000, if we divide the first integer, 100000, by the second 300000, as an integer division, we obtain a quotient of 0, and multiplying by µ still remains at 0. On the other and, if we first multply by µ and then divide by 300000, we obtain 33333, the representation for 0.33333, the good truncated approximation of 1 3 .

To summarize our treatement of division, we can introduce the notation • d ⊘ • for division with rounding towards minus infinity.

n d ⊘ m = n × µ m .
Similar considerations apply for square roots. In particular, there exist algorithms for computing square roots of integers and some of these algorithmes have been implemented and formally verified in proof verification systems [START_REF] Bertot | Interactive Theorem Proving and Program Development, Coq'Art:the Calculus of Inductive Constructions[END_REF][START_REF] Bertot | A proof of GMP square root[END_REF]. It is then possible to implement rounded square root for fixed point computation. In this paper the notation will be ⌊⌋ √ •, and defined as follows:

⌊⌋ √ n = √ n × µ .
All the rounded operations we have considered so far are rounded down, but we will also consider operations rounded up, noted

• u ⊗ •, • u ⊘ •, ⌈⌉ √ •.
These operations are defined in a similar way.

We have already mentioned that addition can be implemented directly using the addition of integers, similarly, multiplication by an integer constant can also be implemented directly by integer multiplication: the integer multiplier should be used directly (not multiplied by the magnification ratio). Also, we should be careful that multiplying an upper bound of a given value by a negative integer will yield a lower bound.

Interval computations

We intend to use the various rounded operations (on integers) to represent elementary operations on real numbers, mostly to compute upper and lower bounds of approximations for polynomial expressions. These polynomial expressions are themselves truncated power series corresponding to the definition of mathematical functions.

Computation setting

We simply need to compute the polynomial expressions with a suitable replacement of the elementary operations by the corresponding integer operations, using rounded up or rounded down approximations as imposed by the sign of the polynomials coefficients.

A particularly interesting case of truncated power series is the case of alternating series, because we know that each truncation is either a lower bound or an upper bound of the expected value. For instance, for the logarithm function, standard mathematical reasoning makes it possible to obtain the following approximation (for 1 ≤ x):

2k+1 n=0 (-1) n (x -1) n+1 n + 1 ≤ ln x ≤ 2k n=0 (-1) n (x -1) n+1 n + 1 .
So, to compute upper and lower bound of ln x for x representable in our fixed point setting, we should simply compute these polynomial expressions using our rounded elementary operations. For instance, we can compute a lower bound the third order expansion in the following way.

(x -1) -((x -1) u ⊗ (x -1)) u ⊘ 2+ (x -1) d ⊗ (x -1) d ⊗ (x -1) d ⊘ 3. preprint 3 2014/10/10
Modern proof systems usually provide language constructs to make recursive definitions available and efficient ways to execute these recursive functions. We can use this ability to define lower and upper bounds of power functions and lower and upper bounds of expansions of power series. In the following, we will use the notations • l ↑ • and • u ↑ • to represent these lower and upper bound power functions.

When one wishes to compute bounds for f (x), for x not representable in our fixed point setting, it is necessary to use the monotonicity of the function f in a neighborhood of x. This usually relies on extra information known about the mathematical function f . When f is known to be increasing (resp. decreasing) in a neighborhood of x, one should first find two representable numbers x1 and x2 in that neighborhood, such that x1 ≤ x ≤ x2 can be proved, and then one only needs to compute a lower bound (resp. upper bound) for f (x1) (resp. f (x2)) and an upper bound (resp. lower bound) for f (x2) (resp. f (x1)) to obtain lower and upper bounds of f (x).

For instance to compute an upper bound of sin √ 2, we only need to know that the sin function is increasing between 0 and π 2 and √ 2 < 1.42 < π 2 and to compute an upper bound of sin(1.42).

Proving bounds

When it comes to proving properties, the main lesson is that we should organize the proof in two stages. In the first stage, we look at the algorithm from the point of view of real numbers and abstract properties of the rounded operations, in the second stage will look at operations on integers and we explain how these operations fulfill the abstract operations. For each of these stages, we define a function that describes exactly the algorithm being verified. We prove the abstract properties in the first stage, using real numbers, and then we show that the second function performs all the same computations but in a concrete setting.

First stage: with real numbers

We should state sufficient properties expected for our rounded functions and only reason using these properties. For our rounded operations, the properties we have chosen to use are the following ones:

0 ≤ a ∧ 0 ≤ b ⇒ 0 ≤ a d ⊗ b ≤ a × b 0 ≤ a ∧ 0 ≤ b ⇒ a × b ≤ a u ⊗ b 0 ≤ a ∧ 1 ≤ b ⇒ a d ⊘ b ≤ a b 0 ≤ a ∧ 1 ≤ b ⇒ a b ≤ a u ⊘ b
These properties are more restrictive than the ones explained informally in section 3. The positivity constraints come from the fact that we decided to avoid questions about how integer division is defined for negative inputs; the constraint about the divisor being larger than 1 is probably an overkill, but it suits the fact that we are mostly interested in series with rational coefficients, so we will only divide by positive integers.

A first proof we can make (by induction on the power) is that the rounded power operations carry over the same properties as the multiplication: the rounded down power of a non-negative value is a lower bound of the power of that value (and is non-negative) and the rounded up power is an upper bound.

For the logarithm function, we describe a function that takes as input a number and a rank (stating how many terms of the series should be computed) and returns a triplet, where the first component is the lower bound of the truncated series at that input number, the second component is the upper bound, and the third component is boolean value that states what was the sign of the last term in the series. The recursive definition is as follows:

ln i(x, 0) = (x, x, true) ln i(x, r + 1) = (a -(x u ↑ r + 2) u ⊘ (r + 2), b -(x d ↑ r + 2) d ⊘ (r + 2), false) when ln i(x, r) = (a, b, true) ln i(x, r + 1) = (a + (x d ↑ r + 2) d ⊘ (r + 2), b + (x u ↑ r + 2) u ⊘ (r + 2), true) when ln i(x, r) = (a, b, false)
We prove quite easily in the domain of real numbers, using proofs by induction on r, that if x is positive and ln i(x, r) = (a, b, c), then c is true exactly when r is even, and the following interval is satisfied:

a ≤ r k=0 (-1) k x k+1 k + 1 ≤ b

Second stage: with integers

We should now make explicit the links between functions on real numbers and integers. At this point, the difference between various proof systems is probably important. Our experiment was performed in the Coq system [START_REF]The Coq proof assistant reference manual[END_REF], where several types of numbers are in use. For this section, we will mostly consider the types of natural numbers, integers, and real numbers. The first two are inductive types, which means that they are algebraic datatypes, and they come with an intrinsic notion of computation. The type nat of natural numbers follows the structure of Peano axioms, so that representing a number n uses an amount of memory propotional to n. The type Z of integers follows the structure of sequences of bits, so that representing a number n uses an amount of memory proportional to log(n). These types also come with pattern-matching and recursive computation, so that the time needed to add n with m is proportional to n for natural numbers and and proportional to max(log(n), log(m) for integers. The type of real numbers is not inductive, and it does not provide any means of computation. Addition, multiplication, and the other operations are only manipulated as abstract operations, with no meaning of computation. However, these operations are known through their properties. For instance, addition is associative and commutative, multiplication distributes and so on. Large integer constants can be written in Coq, but this is only a parsing and displaying trick: when the user types the number 11, the parser actually constructs the following expression:

1 + (1 + 1) * (1 + (1 + 1) * (1 + 1))
One can compute with these expressions quite fast, using the same algorithms as for sequences of bits 2 , In Coq for instance, the tactic called "psatzl R" [START_REF] Besson | Fast reflexive arithmetic tactics the linear case and beyond[END_REF][START_REF] Besson | Modular SMT proofs for fast reflexive checking inside coq[END_REF] takes negligible time to verify the and accept the equality 123456789123456789123456789 + 876543210876543210876543210 ≤ 999999999999999999999999999 but these algorithms only work for real numbers that represent integers, so there is no simple solution when one wants to compare, for instance √ 2 + √ 3 with π. Such a comparison can be made and proved correct, but an ad hoc algorithm must be used. There are bridges between the types nat and Z and the type R. Two functions INR and IZR take as input natural numbers and integers and produce the corresponding real number. In the other direction, there is a function from R to Z that maps any x in R to the smallest integer n in Z such that x ≤ IZR(n). Using this last function, floor and ceiling functions can be defined.

When it comes to representing real numbers with integers in a fixed point setting, we simply map integers to real numbers using the following function (hR is an acronym for high-precision to Real). In this development, we use magnifier as a name for the constant we wrote µ in the mathematical formulas.

hR(n) = IZR(n) / IZR(magnifier)
When it comes to writing the converse, we actually define two functions, which correspond to two rounding modes:

Rh(x) = floor (x * IZR(magnifier)) Rh'(x) = ceiling (x * IZR(magnifier))
Both Rh and Rh' are right inverse to hR, but in general, for any x that is not representable as a fixed precision number, hR(Rh(x)) = x = hR(Rh ′ (x)).

Thanks to its inductive nature, the datatype of integers is equiped with a collection of algorithms, including Euclidean division and square root. The last two actually return pairs of output, where one is the closest integer below the intended real value, and the second one is the remainder. To construct rounded up results of division, it is only necessary to compare this remainder with 0 and act accordingly.

In the end, we define functions as described in section 3 and we prove that they satisfy the properties described in section 4.3. To formulate these properties, we need to use the functions hR, Rh, and Rh'. Here is an example: Lemma up_div_spec : forall x y, 0 <= x -> 1 <= y ->

x / y <= hR (up_div (Rh' x) (Rh y)).

In this statement, up div is a function where all inputs and outputs are integers. Algorithms for computing values eventually manipulate only integers and only use these functions. The proof of correctness for these algorithms only amounts to showing that the computations done on integers mirror exactly the computations done in the same algorithm using the function • u ⊘ •, etc. This could be very easy, but we have to thread the condition that all arguments to all functions are positive in the algorithm correctness proof.

Illustration: computing logarithm bounds

We applied the techniques of this first section to develop a function that computes lower and upper bounds for logarithms. The first step was to define a formal series to compute some logarithm values. This series is simply obtained by observing the properties of the inverse:

1 1 + y = 1 -y + y 2 -y 3 + • • •
More precisely, since the series is alternating, we have the following property

1 -y +y 2 -y 3 • • •-y 2k+1 1 1 + y << 1 -y +y 2 -y 3 +• • •+y 2k .
A well known property of the logarithm function is that its derivative is the inverse function, thus

y - y 2 2 + y 3 3 • • • - y 2k 2k < ln(1 + y)y - y 2 2 + y 3 3 • • • + y 2k+1 2k + 1 .
Substituting x -1 for y in these formulas, we obtain the following comparisons

2k+1 i=0 (-1) i x i+1 i + 1 < ln x < 2k i=0 (-1) i x i+1 i + 1 .
These inequalities are true as soon as x is greater than or equal to 1. For x greater than 2, the series diverges, this means that the bounds provided by these equalities get worse and worse even as the order k increases. Thus, to be able to compute logarithms for values outside the interval [START_REF] Armand | Extending coq with imperative features and its application to SAT verification[END_REF][START_REF] Bertot | Interactive Theorem Proving and Program Development, Coq'Art:the Calculus of Inductive Constructions[END_REF], one needs to apply another technique, known as range reduction. For numbers larger than 2 we chose to rely on square roots. For x in [START_REF] Bertot | Interactive Theorem Proving and Program Development, Coq'Art:the Calculus of Inductive Constructions[END_REF][START_REF] Besson | Fast reflexive arithmetic tactics the linear case and beyond[END_REF], we know that √ x is in [START_REF] Armand | Extending coq with imperative features and its application to SAT verification[END_REF][START_REF] Bertot | Interactive Theorem Proving and Program Development, Coq'Art:the Calculus of Inductive Constructions[END_REF] and we can use the series to compute ln √ x and then conclude by using the following property:

ln x = 2 ln √ x.
Actually, it is also useful to apply this technique in the neighborhood of 2, because it leads to computing the power series at a value around 1.41, and this power series converges much better as one get closer to 1. We chose to implement a function that performs 4 steps of range reduction using square roots. Here is the Coq code for this function. The ( . )%Z expresses that the two values returned in the pair are integers. These integers are bounds for ln n × µ.

Definition ln_approx n p := let v := Z.sqrt (Z.sqrt (Z.sqrt (Z.sqrt (n * magnifier ^15)))) in let '(_, b, _) := ln_i (v + 1 -magnifier) (2 * p) in let '(a, _, _) := ln_i (v -magnifier) (S (2 * p)) in (16 * a, 16 * b)%Z.
The correctness of this function is expressed by the following statement, which has been formally proved: Notice that this statement provides bounds for ln x, but it does not guarantee that these bounds improve when p increases. In practice, this function is useful only when hR(x) < 64, but this fact has not been formally proved.

Intermediate conclusion

In this section we basically described interval computations in a fixed point setting, where all computations are represented using integers. Interval computations mean that we do the computation twice, once for the lower bound and once for the upper bound, making sure to use lower and upper bounds of intermediate results appropriately. In the next section, we will take another approach, which makes it possible to perform the computation once, by computing bounds for the error. This is useful if we want to perform the computation at such a precision that each elementary operation is too costly to be duplicated.

Estimating bounds

Instead of computing lower and upper bounds for the results, we will now compute the errors brought by each approximation, and see how these errors fare in later computations. This will make it possible that sometimes errors compensate in such a way that they ultimately become negligible. This approach will rely on more mathematical properties of the functions being computed, especially the derivative.

A new running example

In their book about properties of the arithmetic-geometric mean [START_REF] Borwein | Pi and the AGM[END_REF], Borwein and Borwein use a sequence defined as follows:

y0 = √ 2 yn+1 = yn + 1 2 √ yn
This sequence converges towards 1, but it is used to construct another sequence that converges towards π very fast (the number of known digits doubles at every iteration). Because of this fast convergence, it is reasonable to use this sequence as the basis for an algorithm to compute large numbers of decimals of the π number (for instance, to compute one million digits, only twenty iterations are required), but all operations must be performed with the same precision. If this precision is really high, we want to avoid performing the same operation twice.

More precise properties of rounded down operations

In section 4.3, we only stated that the rounded down operations gave lower bounds to the result of their exact counterparts. Actually, we could have said something more precise: the distance with the exact operation is actually bounded by a precise value, e = µ -1 . So we should actually use the following properties in our formal reasoning.

0 ≤ a ∧ 0 ≤ b ⇒ a × b -e < a d ⊗ b ≤ a × b 0 ≤ a ∧ 0 < b ⇒ a b -e < a d ⊘ b ≤ a b 0 ≤ a ⇒ √ a -e < ⌊⌋ √ a ≤ √ a
Repeated use of these rounded operations do accumulate errors, of the order of magnitude of e at each step, but the errors obtained from previous operations are modified in a way that depends on the function actually being computed, and it is instrumental to take the global picture into account to see how this modification operates.

Error processing

It is well known that naive interval computation misses opportunities when applied at a level that is too local. The typical example is subtraction. If we know bounds for x and y, say x ∈ [xc -e, xc +e] and y ∈ [yc -e, yc + e], then we know that x -y is an interval obtained by combining both bounds of each input:

x -y ∈ [xc -yc -2e, xc -yc + 2e].
When the inputs are known with a possible error of e, the outputs are known with a possible error of 2e.

If we apply this scheme to x and x, then we are computing x -x, and the result should be 0, exactly. There is no need for an error here. So the naive mechanism of computing bounds for output intervals from the input intervals is particularly inefficient in this case.

The solution we propose in this section is to avoid working with intervals, but instead to work with an explicit error, say h, and to study the difference between the result of our computation when applied to x + h with the result of the exact mathematical value when computed with x.

Expressed in abstract terms, our problem is to compute some value f (x), except that we don't know x exactly we only know a value x + h, where h is unknown but can be bounded, and we don't have a good implementation of f , we only have some other function f , built using approximated elementary operations, which each had some unknown error which can also be bounded. So the value we are actually computing is f (x + h) instead of f (x). Our approach will be to first study f (x + h) -f (x + h) and find a bound, and second to study f (x + h) -f (x) and find a bound.

For instance, in the case of our new running example, we want to compute the distance between 1 + y 2 √ y and

(1 + yh) d ⊘ (2 ⌊⌋ y + h).
Note that we already explained that addition and multiplication by an integer can be performed without adding errors in our setting.

The difference between the exact value and the computed value can be decomposed in two parts: one part comes from the errors of the rounded operations, the other part come from the processing in the input's explicit error, h.

Immediate rounding errors

In this section, we want to study the difference f (x + h) -f (x + h). This study can be analysed by following the structure of the computation, starting from the most external rounded operators.

In the case of our running example, we perform the study in two different steps, one for the upper bound and one for the lower bound.

(1 + y + h) d ⊘ (2 ⌊⌋ y + h) ≤ 1 + y + h 2 ⌊⌋ (y + h) ≤ 1 + y + h 2 × ( √ y + h -e) ≤ 1 + y + h 2 √ y + h + 3 2 × e
In the last step, we use several facts from our context, first y is taken in the interval [1, √ 2], second e is positive and small, and third, 1 1-e < 1 + e + 2e 2 . So already in this example, we see that two rounded operations only add errors of the order of magnitude of three halves of the basic rounding error. These comes from the fact that we are only using rounded down operations, while we are looking at an upper bound of the result, so the division operation actually does not contribute to the rounding error.

A similar study on the other side gives the following lower bound. This time, the square root does not contribute to the rounding error.

1 + y + h 2 √ y + h -e ≤ (1 + y + h) d ⊘ (2 ⌊⌋ y + h)

Error propagation

We now need to study the difference f (x + h) -f (x), since h is supposed to be an error, it is supposed to be small, and a first order approximation using the mean value theorem should suffice. This theorem states that if f is suitably continuous and derivable, then there exists some c between x and x + h such that the difference is the derivative f ′ (c) multiplied by the error h.

f (x + h) -f (x) = f ′ (c) × h
At this stage, context information will be useful, to help keep the derivative f ′ (c) small in absolute value.

In the case of our running example, this means that we need to compute the derivative of the function

y → 1 + y 2 √ y .
This derivative is only valid when y is non-zero and it has the following value: y -1 4y √ y . If we know that y is between 1 and √ 2 and h is smaller than 1/10, then we can guarantee that the derivative is smaller than 1/8 in absolute value, therefore we have the following approximation information:

1 + y + h 2 √ y + h - 1 + y 2 √ y < 1 8 |h|
We see that h is actually reduced in the process: the error coming from previous computations is actually small when compared to the error produced in the last elementary operations. We can then wrap up the study of yn in the following fashion: if division and square root operations are implemented with rounded down mode, with an error of at most e at each operation, and if yn is known with an error does not exceed 2e, then yn+1 is also computed with an error does not exceed 2e (because 3/2 + 1/8 < 2. The intial value is itself computed using a rounded down square root, so the initial error does not exceed e, so we know that all elements of yn will be computed with an error that does not exceed 2e. If we want to compute the elements of this sequence with one million digit of precision, only one million and one digit for intermediate computations will be needed in most cases 3 .

Using big integers

As formalized in the Coq system, addition and comparison should take a time that is proportional to the number of bits of one of the operands. Other operations rely naively on addition and comparisons, so that their complexity grows quite fast. For instance, here is a table comparing the times for comparing 3 n and 5 m , for different values of n and m (actually m is chosen so that the two compared numbers have the same order of magnitude). n, m 100, 68 1000, 682 10000,6827 100000, 68261 time 0.002s 0.07s 5s > 5mn

Other researchers have been using Coq for intensive numerical proofs before [START_REF] Armand | Extending coq with imperative features and its application to SAT verification[END_REF][START_REF] Grégoire | A purely functional library for modular arithmetic and its application to certifying large prime numbers[END_REF] and their library for big integers was integrated in the standard version. In particular, that library re-uses an algorithm for square roots that had been formally proved correct in [START_REF] Bertot | A proof of GMP square root[END_REF]. For instance, the same computations using big integers produce the following table.

n, m 100, 68 1000, 682 10000,6827 100000,68261 time 0.002s 0.003s 0.03s 1.4s

To switch from the basic integer library to the big-integer library, it is enough to replace systematically all elementary operations on integers with elementary operations on big integers. For the correctness proof, we can simply rely on the direct correspondance between integers and big integers. This correspondance is given in the form of theorems with the following shape.

BigZ.spec_mul : forall x y : bigZ, [x * y] = ([x] * [y])%Z

In this theorem the notation [ . ] stands for the function that maps any big integer to the integer it represents. We simply need to push the correspondance through our algorithm, by systematic rewriting, thus obtaining obtaining similar theorems for each of our functions. The only difficulty comes from the functions that do not simply return an integer result, but rather a pair of an integer and a boolean value or a pair of two integers, because the use of these functions does not directly suit proofs based solely on rewriting.

In this big integer library, it is more efficient to compute with a large power of 2 than with a large power of 10. If the goal is to compute one million decimal digits, it is necessary to find the number n such that 10 10 6 < 2 n and provide a proof of this 3 this is tricky only if the millionth digit is 0, 1, 8, or 9.

comparison. This number 4 is simply n = ln 10 ln 2 × 10 6 .

This was the motivation for the first part of this paper. For smaller numbers, developing a dedicated proof to describe formally verified of the bounds is not necessary, it takes only one second to compare 10 10 5 and the suitable power of 2, but the time is multiplied by 30 for 10 10 6 . Once we have chosen a suitable power of 2, we can measure the gain provided by the change from powers of 10 to powers of 2. Computing the integer square root of 2 × 2 2n takes 2/3 of the time to compute the square root of 2 2×10 6 .

Application: computing π to one million digit

In addition to the sequence yn, Borwein and Borwein [START_REF] Borwein | Pi and the AGM[END_REF] give the following sequences 5 that make it possible to compute good approximations of π.

2

  using the pattern (1 + 1) * ... as if it was a bit set to 0 and the pattern 1 + (1 + 1) * ... as if it was a bit set to 1

  ln_approx_correct : forall x, (magnifier < x)%Z -> forall p, let (a, b) := ln_approx x p in hR a <= ln (hR x) <= hR b.

John Machin computed a hundred decimals of π using series expansions of the atan function, in 1706.

and after checking, we know this is satisfied.

40 minutes with 63 bit-integers (version provided by Dénès); an hour and a half with 31 bit-integers (development version of Coq at the time of writing).

8 more minutes). The display routines are not part of the code that was proved formally.

The convergence of πn towards π is expressed by the following comparisons:

0 < πn+1 -π < bn The particular shape of the bound bn expresses that the number of known digits should be multiplied by 2 at each iteration. The mathematical proofs for this result have been formally verified, but this is not the topic of this paper, where we are only concerned with the task of representing the real number of computations in our fixed point setting.

To obtain one million digits of π we must compute a few more digits, to allow for errors coming both from the rounding and errors and from πn -π. Let's first evaluate the rounding errors.

We already showed that the yn values can be computed with an error that does not exceed twice the rounding error of the elementary rounded operations 2 × µ -1 . A similar result makes it possible to show that the accumulated error in zn is only 4 × µ -1 . The next step is to observe the computation of the big product

In the concrete computation, prod, all the inputs representing the values yn and zn are tainted, and moreover the products and divisions also introduce more errors. We were not able to prove the same kind of stability as for yn and zn, but we still get a good bound on the error:

Now, if we name rpi(n) our concrete computation of πn, we get the following bound on the error.

|rpi(n) -πn| < 21n + 2 µ

4 the right value for n is 3321929 5 Actually, Borwein and Borwein use slightly different naming conventions. To compute a million digits of π, we expect n to be around 20, so that the numerator is smaller than 500. Therefore we need to compute approximately 4 extra digits (or 14 extra bits) to help make sure that even the millionth digit is exact. Actually, we need a bit of luck here: even if we compute 4 extra digits and these digits give a number smaller than 400 or larger than 9600, we don't know if the millionth digit is given accurately. For this reason, we implemented a computation with 10 10 6 + 4 digits, obtaining a number N and we then computed N mod 10 4 to check whether we are within the bounds 6 .

If we want to compute one million digits of π, we need to compute the right n so that bn < 10 -10 6

. By computing ln 2 and ln 10 we know that 20 ln 2 > 6 ln 10, therefore 2 20 > 10 6 , and we can conclude using the fact that the logarithm function is strictly increasing. ln b19 = ln(4π0)-2 19 ln 5-2 20 ln 10 ≤ -2 20 ln 10 ≤ -10 6 ln 10

Performing this kind of proof using the logarithm function is more practical than computing directly the big constants and then their logarithms, because the intermediate computations concern values that are not practical. However, in early version of our work, before we implemented a computational version of the logarithm function, relied solely on removing power functions from the formulas to compare. Actually comparing 2 20 and 10 6 is an easy computation that can be integrated directly in the proof.

To summarize the computations that are performed: we compute π20, in binary format, actually computing 3321942 bits, and we then multiply the result by 10 10 6 +4 and divide by 2 3321942 to obtain an approximation of π20×10 10 6 +4 with a possible error less than 1. This computation requires computing twenty high precision square roots, sixty divisions, and forty multiplications. The final result is divided by 10 4 , we check that the remainder is larger than 427 and smaller than 9573. This is enough to guarantee that we computed exactly one million digits of π.

The Coq code describing this process is summarized in the following definition and the lemma pi osix expresses that this definition is correct.

Definition million_digit_pi := let magnifier := (2 ^3321942)%bigZ in let n := hpi magnifier 20 in let n' := (n * 10 ^(10 ^6 + 4) / 2 ^3321942)%bigZ in let (q, r) := BigZ.div_eucl n' (10 ^4) in (((427 <? r)%bigZ && (r <? 9573)%bigZ)%bool, q). pi_osix :

fst million_digit_pi = true -> hR (10 ^(10 ^6)) (snd million_digit_pi) < PI < hR (10 ^(10 ^6)) (snd million_digit_pi) + Rpower 10 (-(Rpower 10 6)).

We ran this code on a powerful computer in two different setting. The first setting relies on virtual machine computation, as designed by B. Grgoire and available in the standard version of Coq 8.4. In this case, execution takes about 6 hours and a half. The second setting relies on native computation as designed by M. Dénès 7 In this case, execution takes approximately forty minutes, not including the time taken by the Coq system to display the result (about