FiniteDifferenceFormula


NameFiniteDifferenceFormula JSON
Version 0.7.8 PyPI version JSON
download
home_page
SummaryA general and comprehensive toolkit for generating finite difference formulas, working with Taylor series expansions, and teaching/learning finite difference formulas in Python
upload_time2023-10-16 15:49:10
maintainer
docs_urlNone
author
requires_python>=3.7
license
keywords calculator coefficients finite difference formula generator
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            # FiniteDifferenceFormula Toolkit

Ported from a Julia package, https://github.com/fdformula/FiniteDifferenceFormula.jl, this
Python package provides a general and comprehensive toolkit for generating finite difference formulas, working with Taylor series expansions,
and teaching/learning finite difference formulas. It generates finite difference formulas
for derivatives of various orders by using Taylor series expansions of a function at evenly
spaced points. It also gives the truncation error of a formula in the big-O notation. We
can use it to generate new formulas in addition to verification of known ones. By changing
decimal places, we can also investigate how rounding errors may affect a result.

Beware, though formulas are mathematically correct, they may not be numerically useful.
This is true especially when we derive formulas for a derivative of higher order. For
example, run compute(9,range(-5, 6)), provided by this package, to generate a 10-point
central formula for the 9-th derivative. The formula is mathematically correct, but it
can hardly be put into use for numerical computing without, if possible, rewriting it
in a special way. Similarly, the more points are used, the more precise a formula
is mathematically. However, due to rounding errors, this may not be true numerically.

To run the code, you need the Python programming language (https://python.org/).

## How to install the package

In OS termial, execute the following command.

- python -m pip install FiniteDifferenceFormula

## The package exports a class, ```FDFormula```, ```fd``` (an object of the class), and the following member functions

```activatepythonfunction```, ```compute```, ```decimalplaces```, ```find```, ```findbackward```,
```findforward```, ```formula```, ```formulas```, ```loadcomputingresults```, ```taylor```,
```taylorcoefs```, ```tcofs```, ```truncationerror```, ```verifyformula```

### functions, ```compute```, ```find```, ```findforward```, and ```findbackward```

All take the same arguments (n, points, printformulaq = False).

#### Input

```
            n: the n-th order derivative to be found
       points: in the format of range(start, stop) or a list
printformulaq: print the computed formula or not
```

|   points       |   The points/nodes to be used                  |
| -------------- | ---------------------------------------------- |
|  range(0,3)    |   x[i], x[i+1], x[i+2]                         |
|  range(-3, 3)  |   x[i-3], x[i-2], x[i-1], x[i], x[i+1], x[i+2] |
|  [1, 0, 1, -1] |   x[i-1], x[i], x[i+1]                         |

A list of points will be rearranged so that elements are ordered
from lowest to highest with duplicate ones removed.

#### Output

Each function returns a tuple, (n, points, k[:], m), where n, points, k[:] and m are described below.
With the information, you may generate functions for any programming language of your choice.

While 'compute' may fail to find a formula using the points, others try to find one, if possible,
by using fewer points in different ways. (See the docstring of each function.)

The algorithm uses the linear combination of f(x[i+j]) = f(x[i] + jh), where h is the increment
in x and j ∈ points, to eliminate f(x[i]), f'(x[i]), f''(x[i]), ..., so that the first nonzero
term of the Taylor series of the linear combination is f^(n)(x[i]).

```Python
k[1]*f(x[i+points[1]]) + k[2]*f(x[i+points[2]]) + ... + k[L]*f(x[i+points[L]]) = m*f^(n)(x[i]) + ..., m > 0
```

where L = len(points) - 1. It is this equation that gives the formula for computing f^(n)(x[i])
and the truncation error in the big-O notation as well.

### function ```loadcomputingresults```(results)

The function loads results, a tuple of the form (n, points, k, m), returned by ```compute```.
For example, it may take hours to compute/find formulas invloving hundreds of points. In this
case, we can save the results in a text file and come back later to work on the results
with ```activatepythonfunction```, ```formula```, ```truncationerror```, and so on.

### function ```formula```()

The function generates and lists

1. k[0]\*f(x[i+points[0]]) + k[1]\*f(x[i+points[1]]) + ... + k[L]\*f(x[i+points[L]])
= m\*f^(n)(x[i]) + ..., where m > 0, L = length(points) - 1

1. The formula for f^(n)(x[i]), including estimation of accuracy in the big-O notation.

1. "Python" function(s) for f^(n)(x[i]).

### function ```truncationerror```()

The function returns a tuple, (n, "O(h^n)"), the truncation error of the newly computed finite
difference formula in the big-O notation.

### function ```decimalplaces```(n = 16)

The function sets to n the decimal places for generating Python function(s) for formulas. It
returns the (new) decimal places. Note: Passing to it a negative integer will return th
present decimal places (without making any changes).

This function can only affect Python functions with the suffix "d" such as f1stderiv2ptcentrald.
See function activatepythonfunction().

### function ```activatepythonfunction```()

Call this function to activate the Python function(s) for the newly computed finite
difference formula. For example, after compute(1, [-1, 0, 1]) and decimalplaces(4), it activates the
following Python functions.

```Python
fde(f, x, i, h)  = ( -f(x[i-1]) + f(x[i+1]) ) / (2 * h)             # i.e., f1stderiv2ptcentrale
fde1(f, x, i, h) = ( -1/2 * f(x[i-1]) + 1/2 * f(x[i+1]) ) / h       # i.e., f1stderiv2ptcentrale1
fdd(f, x, i, h)  = ( -0.5000 * f(x[i-1]) + 0.5000 * f(x[i+1]) ) / h # i.e., f1stderiv2ptcentrald
```
The suffixes 'e' and 'd' stand for 'exact' and 'decimal', respectively. No suffix? It is "exact".
After activating the function(s), we can evaluate right away in the present Python REPL session. For example,

```Python
fd.compute(1, range(-10,9))
fd.activatepythonfunction()
fd.fde(sin, [ 0.01*i for i in range(0, 1000)], 501, 0.01)
```
Below is the output of activatepythonfunction(). It gives us the first chance to examine the usability
of the computed or tested formula.

```Python
f, x, i, h = sin, [ 0.01*i for i in range(0, 1000) ], 501, 0.01
fd.fde(f, x, i, h)   # result: 0.2836574577837647, relative error = 0.00166666%
fd.fde1(f, x, i, h)  # result: 0.2836574577837647, relative error = 0.00166666%
fd.fdd(f, x, i, h)   # result: 0.2836574577837647, relative error = 0.00166666%
                     # cp:     0.2836621854632262
```

### function ```verifyformula```(n, points, k, m)

It allows users to load a formula from some source to test and see if it is correct. If it is valid,
its truncation error in the big-O notation can be determined. Furthermore, if the input data is not
for a valid formula, it tries also to find one, if possible, using n and points.

Here, n is the order of a derivative, points are a list of points, k is a list of the corresponding
coefficients of a formula, and m is the coefficient of the term f^(n)(x[i]) in the linear
combination of f(x[i+j]), where j ∈ points. In general, m is the coefficient of h^n in the
denominator of a formula. For example,

```Python
fd.verifyformula(2, [-1, 0, 2, 3, 6], [12, 21, 2, -3, -9], -12)
fd.truncationerror()
fd.verifyformula(4, [0, 1, 2, 3, 4], [2/5, -8/5, 12/5, -8/3, 2/5], 5)
fd.verifyformula(2, [-1, 2, 0, 2, 3, 6], [1.257, 21.16, 2.01, -3.123, -9.5], -12)
```

### function ```taylorcoefs```(j, n = 10) or ```tcoefs```(j, n = 10)

The function returns the coefficients of the first n terms of the Taylor series of f(x[i+j])
about x[i].

### function ```taylor```(j, n = 10)

The function prints the first n terms of the Taylor series of f(x[i+j]) about x[i].

### function ```taylor```(coefficients_of_taylor_series, n = 10)

The function prints the first n nonzero terms of a Taylor series of which the coefficients are
provided.

### function ```taylor```((points, k), n = 10)

The function prints the first n nonzero terms of a Taylor series of which the linear combination
of k[0]f(x[i+points[0]]) + k[1]f(x[i+points[1]]) + ... + k[L]f(x[i+points[L]]), where L = len(points).

### function ```formulas```(orders = [1, 2, 3], min_num_of_points = 2, max_num_of_points = 5)

By default, the function prints all forward, backward, and central finite difference formulas for
the 1st, 2nd, and 3rd derivatives, using 2 to 5 points.

## Examples

```Python
from FiniteDifferenceFormula import fd
fd.compute(1, range(0,3), True)        # find, generate, and print "3"-point forward formula for f'(x[i])
fd.compute(2, range(-3,1), True)       # find, generate, and print "4"-point backward formula for f''(x[i])
fd.compute(3, range(-9,10))            # find "19"-point central formula for f'''(x[i])
fd.decimalplaces(6)                    # use 6 decimal places to generate Python functions of computed formulas
fd.compute(2, [-3, -2, 1, 2, 7])       # find formula for f''(x[i]) using points x[i+j], j = -3, -2, 1, 2, and 7
fd.compute(1, range(-230, 231))        # find "461"-point central formula for f'(x[i]). does it exist? run the code!
fd.formula()                           # generate and print the formula computed last time you called compute(...)
fd.truncationerror()                   # print and return the truncation error of the newly computed formula
fd.taylor(-2, 50)                      # print the first 50 terms of the Taylor series of f(x[i-2]) about x[i]

import numpy as np
coefs  = -2 * np.array(fd.tcoefs(1)) + 3 * np.array(fd.tcoefs(2)) - 4 * np.array(fd.tcoefs(5))
fd.taylor(list(coefs), 9)              # print the first 9 nonzero terms of the Taylor series of -2f(x[i+1) + 3f(x[i+2]) - 4f(x[i+5])

fd.taylor(([1, 2, 5], [-2, 3, -4]), 9) # same as above

fd.activatepythonfunction()            # activate Python function(s) of the newly computed formula in present REPL session
fd.verifyformula(1, [2,3], [-4, 5], 6) # verify if f'(x[i]) = (-4f(x[i+2] + 5f(x[i+3)) / (6h) is a valid formula
fd.formulas(2, 5, 9)                   # print all forward, backword, and central formulas for the 2nd derivative, using 5 to 9 points
fd.formulas([2, 4], 5, 9)              # print all forward, backword, and central formulas for the 2nd and 4th derivatives, using 5 to 9 points
```

            

Raw data

            {
    "_id": null,
    "home_page": "",
    "name": "FiniteDifferenceFormula",
    "maintainer": "",
    "docs_url": null,
    "requires_python": ">=3.7",
    "maintainer_email": "David Wang <dwang2000@gmail.com>",
    "keywords": "calculator,coefficients,finite difference,formula,generator",
    "author": "",
    "author_email": "David Wang <dwang2000@gmail.com>",
    "download_url": "https://files.pythonhosted.org/packages/bb/97/b79ccd8146ba25c9638dc827eb53c47bd2e800b17f1dda4e017670dbcf38/finitedifferenceformula-0.7.8.tar.gz",
    "platform": null,
    "description": "# FiniteDifferenceFormula Toolkit\n\nPorted from a Julia package, https://github.com/fdformula/FiniteDifferenceFormula.jl, this\nPython package provides a general and comprehensive toolkit for generating finite difference formulas, working with Taylor series expansions,\nand teaching/learning finite difference formulas. It generates finite difference formulas\nfor derivatives of various orders by using Taylor series expansions of a function at evenly\nspaced points. It also gives the truncation error of a formula in the big-O notation. We\ncan use it to generate new formulas in addition to verification of known ones. By changing\ndecimal places, we can also investigate how rounding errors may affect a result.\n\nBeware, though formulas are mathematically correct, they may not be numerically useful.\nThis is true especially when we derive formulas for a derivative of higher order. For\nexample, run compute(9,range(-5, 6)), provided by this package, to generate a 10-point\ncentral formula for the 9-th derivative. The formula is mathematically correct, but it\ncan hardly be put into use for numerical computing without, if possible, rewriting it\nin a special way. Similarly, the more points are used, the more precise a formula\nis mathematically. However, due to rounding errors, this may not be true numerically.\n\nTo run the code, you need the Python programming language (https://python.org/).\n\n## How to install the package\n\nIn OS termial, execute the following command.\n\n- python -m pip install FiniteDifferenceFormula\n\n## The package exports a class, ```FDFormula```, ```fd``` (an object of the class), and the following member functions\n\n```activatepythonfunction```, ```compute```, ```decimalplaces```, ```find```, ```findbackward```,\n```findforward```, ```formula```, ```formulas```, ```loadcomputingresults```, ```taylor```,\n```taylorcoefs```, ```tcofs```, ```truncationerror```, ```verifyformula```\n\n### functions, ```compute```, ```find```, ```findforward```, and ```findbackward```\n\nAll take the same arguments (n, points, printformulaq = False).\n\n#### Input\n\n```\n            n: the n-th order derivative to be found\n       points: in the format of range(start, stop) or a list\nprintformulaq: print the computed formula or not\n```\n\n|   points       |   The points/nodes to be used                  |\n| -------------- | ---------------------------------------------- |\n|  range(0,3)    |   x[i], x[i+1], x[i+2]                         |\n|  range(-3, 3)  |   x[i-3], x[i-2], x[i-1], x[i], x[i+1], x[i+2] |\n|  [1, 0, 1, -1] |   x[i-1], x[i], x[i+1]                         |\n\nA list of points will be rearranged so that elements are ordered\nfrom lowest to highest with duplicate ones removed.\n\n#### Output\n\nEach function returns a tuple, (n, points, k[:], m), where n, points, k[:] and m are described below.\nWith the information, you may generate functions for any programming language of your choice.\n\nWhile 'compute' may fail to find a formula using the points, others try to find one, if possible,\nby using fewer points in different ways. (See the docstring of each function.)\n\nThe algorithm uses the linear combination of f(x[i+j]) = f(x[i] + jh), where h is the increment\nin x and j \u2208 points, to eliminate f(x[i]), f'(x[i]), f''(x[i]), ..., so that the first nonzero\nterm of the Taylor series of the linear combination is f^(n)(x[i]).\n\n```Python\nk[1]*f(x[i+points[1]]) + k[2]*f(x[i+points[2]]) + ... + k[L]*f(x[i+points[L]]) = m*f^(n)(x[i]) + ..., m > 0\n```\n\nwhere L = len(points) - 1. It is this equation that gives the formula for computing f^(n)(x[i])\nand the truncation error in the big-O notation as well.\n\n### function ```loadcomputingresults```(results)\n\nThe function loads results, a tuple of the form (n, points, k, m), returned by ```compute```.\nFor example, it may take hours to compute/find formulas invloving hundreds of points. In this\ncase, we can save the results in a text file and come back later to work on the results\nwith ```activatepythonfunction```, ```formula```, ```truncationerror```, and so on.\n\n### function ```formula```()\n\nThe function generates and lists\n\n1. k[0]\\*f(x[i+points[0]]) + k[1]\\*f(x[i+points[1]]) + ... + k[L]\\*f(x[i+points[L]])\n= m\\*f^(n)(x[i]) + ..., where m > 0, L = length(points) - 1\n\n1. The formula for f^(n)(x[i]), including estimation of accuracy in the big-O notation.\n\n1. \"Python\" function(s) for f^(n)(x[i]).\n\n### function ```truncationerror```()\n\nThe function returns a tuple, (n, \"O(h^n)\"), the truncation error of the newly computed finite\ndifference formula in the big-O notation.\n\n### function ```decimalplaces```(n = 16)\n\nThe function sets to n the decimal places for generating Python function(s) for formulas. It\nreturns the (new) decimal places. Note: Passing to it a negative integer will return th\npresent decimal places (without making any changes).\n\nThis function can only affect Python functions with the suffix \"d\" such as f1stderiv2ptcentrald.\nSee function activatepythonfunction().\n\n### function ```activatepythonfunction```()\n\nCall this function to activate the Python function(s) for the newly computed finite\ndifference formula. For example, after compute(1, [-1, 0, 1]) and decimalplaces(4), it activates the\nfollowing Python functions.\n\n```Python\nfde(f, x, i, h)  = ( -f(x[i-1]) + f(x[i+1]) ) / (2 * h)             # i.e., f1stderiv2ptcentrale\nfde1(f, x, i, h) = ( -1/2 * f(x[i-1]) + 1/2 * f(x[i+1]) ) / h       # i.e., f1stderiv2ptcentrale1\nfdd(f, x, i, h)  = ( -0.5000 * f(x[i-1]) + 0.5000 * f(x[i+1]) ) / h # i.e., f1stderiv2ptcentrald\n```\nThe suffixes 'e' and 'd' stand for 'exact' and 'decimal', respectively. No suffix? It is \"exact\".\nAfter activating the function(s), we can evaluate right away in the present Python REPL session. For example,\n\n```Python\nfd.compute(1, range(-10,9))\nfd.activatepythonfunction()\nfd.fde(sin, [ 0.01*i for i in range(0, 1000)], 501, 0.01)\n```\nBelow is the output of activatepythonfunction(). It gives us the first chance to examine the usability\nof the computed or tested formula.\n\n```Python\nf, x, i, h = sin, [ 0.01*i for i in range(0, 1000) ], 501, 0.01\nfd.fde(f, x, i, h)   # result: 0.2836574577837647, relative error = 0.00166666%\nfd.fde1(f, x, i, h)  # result: 0.2836574577837647, relative error = 0.00166666%\nfd.fdd(f, x, i, h)   # result: 0.2836574577837647, relative error = 0.00166666%\n                     # cp:     0.2836621854632262\n```\n\n### function ```verifyformula```(n, points, k, m)\n\nIt allows users to load a formula from some source to test and see if it is correct. If it is valid,\nits truncation error in the big-O notation can be determined. Furthermore, if the input data is not\nfor a valid formula, it tries also to find one, if possible, using n and points.\n\nHere, n is the order of a derivative, points are a list of points, k is a list of the corresponding\ncoefficients of a formula, and m is the coefficient of the term f^(n)(x[i]) in the linear\ncombination of f(x[i+j]), where j \u2208 points. In general, m is the coefficient of h^n in the\ndenominator of a formula. For example,\n\n```Python\nfd.verifyformula(2, [-1, 0, 2, 3, 6], [12, 21, 2, -3, -9], -12)\nfd.truncationerror()\nfd.verifyformula(4, [0, 1, 2, 3, 4], [2/5, -8/5, 12/5, -8/3, 2/5], 5)\nfd.verifyformula(2, [-1, 2, 0, 2, 3, 6], [1.257, 21.16, 2.01, -3.123, -9.5], -12)\n```\n\n### function ```taylorcoefs```(j, n = 10) or ```tcoefs```(j, n = 10)\n\nThe function returns the coefficients of the first n terms of the Taylor series of f(x[i+j])\nabout x[i].\n\n### function ```taylor```(j, n = 10)\n\nThe function prints the first n terms of the Taylor series of f(x[i+j]) about x[i].\n\n### function ```taylor```(coefficients_of_taylor_series, n = 10)\n\nThe function prints the first n nonzero terms of a Taylor series of which the coefficients are\nprovided.\n\n### function ```taylor```((points, k), n = 10)\n\nThe function prints the first n nonzero terms of a Taylor series of which the linear combination\nof k[0]f(x[i+points[0]]) + k[1]f(x[i+points[1]]) + ... + k[L]f(x[i+points[L]]), where L = len(points).\n\n### function ```formulas```(orders = [1, 2, 3], min_num_of_points = 2, max_num_of_points = 5)\n\nBy default, the function prints all forward, backward, and central finite difference formulas for\nthe 1st, 2nd, and 3rd derivatives, using 2 to 5 points.\n\n## Examples\n\n```Python\nfrom FiniteDifferenceFormula import fd\nfd.compute(1, range(0,3), True)        # find, generate, and print \"3\"-point forward formula for f'(x[i])\nfd.compute(2, range(-3,1), True)       # find, generate, and print \"4\"-point backward formula for f''(x[i])\nfd.compute(3, range(-9,10))            # find \"19\"-point central formula for f'''(x[i])\nfd.decimalplaces(6)                    # use 6 decimal places to generate Python functions of computed formulas\nfd.compute(2, [-3, -2, 1, 2, 7])       # find formula for f''(x[i]) using points x[i+j], j = -3, -2, 1, 2, and 7\nfd.compute(1, range(-230, 231))        # find \"461\"-point central formula for f'(x[i]). does it exist? run the code!\nfd.formula()                           # generate and print the formula computed last time you called compute(...)\nfd.truncationerror()                   # print and return the truncation error of the newly computed formula\nfd.taylor(-2, 50)                      # print the first 50 terms of the Taylor series of f(x[i-2]) about x[i]\n\nimport numpy as np\ncoefs  = -2 * np.array(fd.tcoefs(1)) + 3 * np.array(fd.tcoefs(2)) - 4 * np.array(fd.tcoefs(5))\nfd.taylor(list(coefs), 9)              # print the first 9 nonzero terms of the Taylor series of -2f(x[i+1) + 3f(x[i+2]) - 4f(x[i+5])\n\nfd.taylor(([1, 2, 5], [-2, 3, -4]), 9) # same as above\n\nfd.activatepythonfunction()            # activate Python function(s) of the newly computed formula in present REPL session\nfd.verifyformula(1, [2,3], [-4, 5], 6) # verify if f'(x[i]) = (-4f(x[i+2] + 5f(x[i+3)) / (6h) is a valid formula\nfd.formulas(2, 5, 9)                   # print all forward, backword, and central formulas for the 2nd derivative, using 5 to 9 points\nfd.formulas([2, 4], 5, 9)              # print all forward, backword, and central formulas for the 2nd and 4th derivatives, using 5 to 9 points\n```\n",
    "bugtrack_url": null,
    "license": "",
    "summary": "A general and comprehensive toolkit for generating finite difference formulas, working with Taylor series expansions, and teaching/learning finite difference formulas in Python",
    "version": "0.7.8",
    "project_urls": {
        "Homepage": "https://github.com/Winux2k/FiniteDifferenceFormula.py"
    },
    "split_keywords": [
        "calculator",
        "coefficients",
        "finite difference",
        "formula",
        "generator"
    ],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "f9a24607ab117b572f2de38b2b4ce1d9f96d269d275460bd9814d8c50944aa29",
                "md5": "8757cd9b0022a3c5d2acecf4a00bb9e6",
                "sha256": "071891035f42f1d83890519397d13629e1a3e65ce86123ad6cfc30b0fe13276d"
            },
            "downloads": -1,
            "filename": "finitedifferenceformula-0.7.8-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "8757cd9b0022a3c5d2acecf4a00bb9e6",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.7",
            "size": 21059,
            "upload_time": "2023-10-16T15:49:08",
            "upload_time_iso_8601": "2023-10-16T15:49:08.940844Z",
            "url": "https://files.pythonhosted.org/packages/f9/a2/4607ab117b572f2de38b2b4ce1d9f96d269d275460bd9814d8c50944aa29/finitedifferenceformula-0.7.8-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "bb97b79ccd8146ba25c9638dc827eb53c47bd2e800b17f1dda4e017670dbcf38",
                "md5": "95d5938b9fc0c3b1813b0bea00bcac65",
                "sha256": "c0afe07164e21f9523890c042619024a1996861d12b17d47ca446503264303ce"
            },
            "downloads": -1,
            "filename": "finitedifferenceformula-0.7.8.tar.gz",
            "has_sig": false,
            "md5_digest": "95d5938b9fc0c3b1813b0bea00bcac65",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.7",
            "size": 19246,
            "upload_time": "2023-10-16T15:49:10",
            "upload_time_iso_8601": "2023-10-16T15:49:10.710785Z",
            "url": "https://files.pythonhosted.org/packages/bb/97/b79ccd8146ba25c9638dc827eb53c47bd2e800b17f1dda4e017670dbcf38/finitedifferenceformula-0.7.8.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2023-10-16 15:49:10",
    "github": true,
    "gitlab": false,
    "bitbucket": false,
    "codeberg": false,
    "github_user": "Winux2k",
    "github_project": "FiniteDifferenceFormula.py",
    "travis_ci": false,
    "coveralls": false,
    "github_actions": false,
    "lcname": "finitedifferenceformula"
}
        
Elapsed time: 1.58647s