Algorithms and software for increasing of the calculation speed on personal computers
Acceleration of time-consuming calculations is discussed.
Saved in:
| Published in: | Вопросы атомной науки и техники |
|---|---|
| Date: | 2001 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Національний науковий центр «Харківський фізико-технічний інститут» НАН України
2001
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/78452 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Algorithms and software for increasing of the calculation speed on personal computers / I.N. Shapoval, E.V. Krivorukov // Вопросы атомной науки и техники. — 2001. — № 1. — С. 71-72. — Бібліогр.: 5 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859914049252229120 |
|---|---|
| author | Shapoval, I.N. Krivorukov, E.V. |
| author_facet | Shapoval, I.N. Krivorukov, E.V. |
| citation_txt | Algorithms and software for increasing of the calculation speed on personal computers / I.N. Shapoval, E.V. Krivorukov // Вопросы атомной науки и техники. — 2001. — № 1. — С. 71-72. — Бібліогр.: 5 назв. — англ. |
| collection | DSpace DC |
| container_title | Вопросы атомной науки и техники |
| description | Acceleration of time-consuming calculations is discussed.
|
| first_indexed | 2025-12-07T16:04:11Z |
| format | Article |
| fulltext |
ALGORITHMS AND SOFTWARE FOR INCREASING
OF THE CALCULATION SPEED ON PERSONAL COMPUTERS
I.N. Shapoval, E.V. Krivorukov
National Science Center “Kharkov Institute of Physics and Technology”, Kharkov, Ukraine
Acceleration of time-consuming calculations is discussed.
PACS: 61.20.-Ja.
1. INTRODUCTION
When improvement of elemental base productivity
began approaching to physical limits and a cost factor
commenced to play a significant role the multiprocessor
systems have started to develop by quick pace. But the
world experience shows that at all steps of computing
technique development also an important way of reduc-
ing the time of obtaining calculation results is a choice
of optimal decision algorithms and their programmed
realization. Among these are the table-algorithmic
methods (TAM) of function calculation being widely
applied and at the same time the most effective.
In the present paper considered are the results of ap-
plication of TAM for increasing the speed of calcula-
tions the essence of which consists in the use of a high-
er-speed function approximation by reference values as
compared to direct calculations. The results known in
this field [1-5] were obtained mainly for universal com-
puters processing a large memory. However, in connec-
tion with significant increasing the operational memory
capacity (as a rule exceeding 32 MB) in personal com-
puters of latter generations and due to vigorous widen-
ing a sphere of their application, of a great interest is the
development and use of TAM for increasing the speed
of calculations on PC depending on the features of their
technological and system architecture.
Let us consider briefly the problem statement (in
more details this is given in authors’ paper [4]).
As is well-known, a direct calculation of a wide
class of functions in the vicinity of the point x0∈ [a, b]
can be replaced by executing the approximation of a
function by its reference values, e.g. by polynomials of
a special form or by truncated series expansion of this
function. The calculation of the function f(x) is realized
by a set of operations {/, *, ±, sampling from the memo-
ry} arranged in order of decreasing times of execution
t1>t2>...≥/ t4 corresponding to the operation. Thus, the
calculation time f(x) tf= Σ ti ni for the selected calcula-
tion environment is determined by the set nf=
{n1,n2,...,n4}, where n1 equals to the number of division
operations, n2 - to the multiplication operations etc.
Therefore, decrease of the calculation time can be
achieved by reducing either all or first components at
the expense of latter ones of the nf set.
When selecting the algorithm of high-speed function
calculation, the optimization by the nf set in propagated
TAM realizations leads to such significant increase in
volumes of function reference tables (RT), and so to in-
crease in time expenditures for search of adequate func-
tion nods in RT, that this can result in an effect being di-
rectly contrary to the expected speed increasing. Tend-
ing to obtain an acceptable accuracy of approximations
without increasing table volumes in turn increases the
time expenditures being reciprocal to the expected gain.
So, for example, it is well known that the use of the best
Chebyshev approximation provides the best uniform ap-
proximation among polynomials of the set exponent.
However, then a significant time is spent for search of
alternance points and for calculation of polynomial co-
efficients. Thus, we have before us the problem of find-
ing a TAM realization with which the effect of increas-
ing the speed of a directly approximating calculation
does not lead to the competitive increase of time expen-
ditures to support this approximation. In this respect
adaptive aspects of RT applying emerge as a decisive
factor.
Let us introduce the set n*={n1
*,n2
*,...,n5
*}, represent-
ing the function approximation operations by the opti-
mally selected series : certainly, this set and the time of
its realization t*=Σ ti ni
* should not be dependent on the
choice of a function. Let tт
f is the time necessary for
construction by the reference points df of the RT func-
tion f(x) , which should be constructed and used taking
in mind assurance of the acceptable accuracy of calcula-
tion approximation.
To estimate the effectiveness of TAM realizations
developed we determine the coefficients Ka- of reducing
the time of proper calculation and Kf - of reducing the
time of full calculation. Then for a calculation session in
which the function is calculated Mf times, Mf >> df , the
coefficients introduced take the form
t*)) d - M( t /( tM K/ t*, t K ff
f
mfff fa +== (1)
And with fixed tf, tт
f, df, t*, it is evident
aK→fK (2)
together with the increase of Mf . Such a situation takes
place, of course, in calculation sessions where the num-
ber of function calls is accompanied by the essential lo-
calization of the function argument values.
A specific feature of universal computers designed
for a wide range of problems has in consequence forma-
tion of universal software. Therefore, the programmed
realization of TAM on a universal computer inevitably
increases RT dimensions while embracing classes of
problems or extending the range of function determina-
tion. This observation is confirmed also by TAM real-
ization for set functions that have been performed in
leading computer firms. In [4] one describes the realiza-
tion allowing obtaining an appreciable acceleration of
calculation. The mentioned above realization means in
PROBLEMS OF ATOMIC SCIENCE AND TECHNOLOGY. 2001, № 1.
Series: Nuclear Physics Investigations (37), p. 71-72.
71
essence a personalization of calculations on universal
computers.
In connection with an extensive application of PC
and increase of their memory resource it is seem natu-
rally to transfer and develop further TAM on PC. The
present paper is aimed at presenting such a direction of
calculation speed increase.
2. ADAPTIVE TAM REALIZATIONS
The calculation speed increase is based, according to
formula (1), on reducing calculation for a wide class of
functions to the standard approximation of functions
over its self-stored reference values, so the effect of cal-
culation time reducing within large sessions localized
by calculation argument values approaches to the coeffi-
cient Ka in correspondence with (2). In this case the
speed of this approximation is determined only by the
character of RT construction.
The table gives the estimations for Ka obtained in a
numerical experiment on PC being analogous to coeffi-
cients of calculation time reducing on universal comput-
ers obtained earlier. Their realization in С++ language,
under conditions when a user has at its disposal practi-
cally unlimited resources of the operative memory and
PC on the whole, of course, allows one to solve optimal-
ly the problem of direct approximation of calculations
executed in short time tт
f.
Function Ka
x16/(1-x8) 7.
Integral Sine 4.
Gamma- function 2.5
Complete elliptic integral of the first kind 6.5
Generalized complete elliptic integral 8.0
Bessel function 70.
An important constituent part of TAM for increasing
the speed of calculation are the operations with RT:
their intrinsic organization, technique of finding nods in
RT being the most suitable for approximation, ways of
completing RT with new nodal values of a given func-
tion. As effective are the following mode of adaptive
TAM realizations:
−table with intervals (is constructed immediately after
as-determined interval),
−discrete RT (RT is completed with as-calculated nods,
−RT with one reference point (when the function argu-
ment changes monotonically).
Each of above listed modes of RT use has its own
domain of preference determined by the function form
and character of distributions required in the course of
calculating the function argument values.
If in the calculation mix dominating in time are the
parts being accelerated, then the total acceleration in the
limit of large sessions, approaching to Ka, can be signifi-
cant. The degree of approximation depends, as is shown
in [4], on the spatial organization of RT, the order of ap-
pearance of values in the calculation session completing
RT, and on the calculation volume.
A representative bank of results of TAM application
for acceleration of calculations and effective algorithms
of their realization are formed during development and
generalization of experience in their service.
3. DEVELOPMENT OF TAM
On the base of tested algorithms used for increasing
the speed of calculation of one-variable functions the
following methods should be developed:
−direct methods for table-algorithmic accelerating the
calculation of several-variables functions;
−methods of dimensionality model reduction for the
available functional dependence or for its required do-
main of argument changes, and development, on the
base of these methods, of TAM for increasing the speed
of calculation;
−construction of space filling curves (Peano curves) for
many-dimensional domains of function determining.
Reducing of TAM for increasing the speed of calcula-
tion of many- variable functions to the table-algorithmic
accelerating the calculation of one-variable function via
superposition of the starting function and Peano map-
ping;
−TAM for increasing the speed of calculating the «by
measure» functions i.e. approximating the given func-
tion with an acceptable accuracy, excepting a set of ar-
gument values with the measure of a set small value in
which the function calculated directly and its “TAM
equivalent” can differ considerably.
4. CONCLUSIONS
The necessity of application and development in the
PC environment of executed TAM with an experience of
using them for universal computers is substantiated. On
the base of the expected acceleration it is shown that
one should hope for considerable acceleration of time-
consuming calculations when localizing domains of
their determination.
REFERENCES
1. B.A. Popov, G.S.Tesler Approximation of functions
for technological applications- Kiev: “Naukova
dumka” (in Russian).
2. A.B. Vasil’ev at al. Table-algorithmic method for
function calculation for universal microcomputers.
L.: Publ. H. of Inst. of precise mechanics and optics,
1985, v. 3, p. 621 (in Russian).
3. V.I. Potapov, A.I. Florensov Table−algorithmic cal-
culation of functions on computers. Irkutsk: Publ.
House, 1985, p. 107 (in Russian).
4. E.V. Krivorukov, I.N. Shapoval. Programmed real-
ization of table-algorithmic acceleration of function
calculation. Programming. 1989, №3, p.78-87 (R).
5. E.V. Krivorukov, I.N. Shapoval. Development of al-
gorithmic methods of increasing the speed of calcu-
lations // VANT. Ser. Yad. fiz. issledovaniya, №1
(33), 1999, p. 123-124 (in Russian).
72
I.N. Shapoval, E.V. Krivorukov
National Science Center “Kharkov Institute of Physics and Technology”, Kharkov, Ukraine
Acceleration of time-consuming calculations is discussed.
1. INTRODUCTION
2. ADAPTIVE TAM REALIZATIONS
The necessity of application and development in the PC environment of executed TAM with an experience of using them for universal computers is substantiated. On the base of the expected acceleration it is shown that one should hope for considerable acceleration of time-consuming calculations when localizing domains of their determination.
REFERENCES
|
| id | nasplib_isofts_kiev_ua-123456789-78452 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1562-6016 |
| language | English |
| last_indexed | 2025-12-07T16:04:11Z |
| publishDate | 2001 |
| publisher | Національний науковий центр «Харківський фізико-технічний інститут» НАН України |
| record_format | dspace |
| spelling | Shapoval, I.N. Krivorukov, E.V. 2015-03-17T12:16:25Z 2015-03-17T12:16:25Z 2001 Algorithms and software for increasing of the calculation speed on personal computers / I.N. Shapoval, E.V. Krivorukov // Вопросы атомной науки и техники. — 2001. — № 1. — С. 71-72. — Бібліогр.: 5 назв. — англ. 1562-6016 PACS: 61.20.-Ja. https://nasplib.isofts.kiev.ua/handle/123456789/78452 Acceleration of time-consuming calculations is discussed. en Національний науковий центр «Харківський фізико-технічний інститут» НАН України Вопросы атомной науки и техники Experimental methods and computations Algorithms and software for increasing of the calculation speed on personal computers Алгоритмы и программное обеспечение ускорения вычислений на ПК Article published earlier |
| spellingShingle | Algorithms and software for increasing of the calculation speed on personal computers Shapoval, I.N. Krivorukov, E.V. Experimental methods and computations |
| title | Algorithms and software for increasing of the calculation speed on personal computers |
| title_alt | Алгоритмы и программное обеспечение ускорения вычислений на ПК |
| title_full | Algorithms and software for increasing of the calculation speed on personal computers |
| title_fullStr | Algorithms and software for increasing of the calculation speed on personal computers |
| title_full_unstemmed | Algorithms and software for increasing of the calculation speed on personal computers |
| title_short | Algorithms and software for increasing of the calculation speed on personal computers |
| title_sort | algorithms and software for increasing of the calculation speed on personal computers |
| topic | Experimental methods and computations |
| topic_facet | Experimental methods and computations |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/78452 |
| work_keys_str_mv | AT shapovalin algorithmsandsoftwareforincreasingofthecalculationspeedonpersonalcomputers AT krivorukovev algorithmsandsoftwareforincreasingofthecalculationspeedonpersonalcomputers AT shapovalin algoritmyiprogrammnoeobespečenieuskoreniâvyčisleniinapk AT krivorukovev algoritmyiprogrammnoeobespečenieuskoreniâvyčisleniinapk |