41 results on '"Approximate arithmetic"'
Search Results
2. Spatial Biases in Approximate Arithmetic Are Subject to Sequential Dependency Effects and Dissociate From Attentional Biases
- Author
-
Maria Glaser and André Knops
- Subjects
spatial biases ,mnl ,approximate arithmetic ,numerical cognition ,operational momentum ,Psychology ,BF1-990 ,Mathematics ,QA1-939 - Abstract
The notion that mental arithmetic is associated with shifts of spatial attention along a spatially organised mental number representation has received empirical support from three lines of research. First, participants tend to overestimate results of addition and underestimate those of subtraction problems in both exact and approximate formats. This has been termed the operational momentum (OM) effect. Second, participants are faster in detecting right-sided targets presented in the course of addition problems and left-sided targets in subtraction problems (attentional bias). Third, participants are biased toward choosing right-sided response alternatives to indicate the results of addition problems and left-sided response alternatives for subtraction problems (Spatial Association Of Responses [SOAR] effect). These effects potentially have their origin in operation-specific shifts of attention along a spatially organised mental number representation: rightward for addition and leftward for subtraction. Using a lateralised target detection task during the calculation phase of non-symbolic additions and subtractions, the current study measured the attentional focus, the OM and SOAR effects. In two experiments, we replicated the OM and SOAR effects but did not observe operation-specific biases in the lateralised target-detection task. We describe two new characteristics of the OM effect: First, a time-resolved, block-wise analysis of both experiments revealed sequential dependency effects in that the OM effect builds up over the course of the experiment, driven by the increasing underestimation of subtraction over time. Second, the OM effect was enhanced after arithmetic operation repetition compared to trials where arithmetic operation switched from one trial to the next. These results call into question the operation-specific attentional biases as the sole generator of the observed effects and point to the involvement of additional, potentially decisional processes that operate across trials.
- Published
- 2023
- Full Text
- View/download PDF
3. A BRIEF SUMMARY OF THE FULL RNS VARIANT OF SOME HOMOMORPHIC ENCRYPTIONS.
- Author
-
Hati, Nargiz Khankishiyeva
- Subjects
ARITHMETIC ,CRYPTOGRAPHY ,APPROXIMATION theory ,MATHEMATICAL formulas ,MATHEMATICAL analysis - Abstract
Since discovery of fully homomorphic encryption by Gentry in 2009, interest of lattice-based cryptography has significantly increased. Several researches have improved the efficiency of homomorphic encryption (HE) schemes. Despite all those powerful results, huge computational cost of underlying operations limits feasibility of practical implementations. In order to avoid computations over large numbers, residue number system arithmetic was included into HE cryptosystems scheme. In this paper, residue number system (RNS) and its representation were introduced and applications of RNS representation in some homomorphic encryptions was presented and some of them are analyzed extensively. This paper aims to present a brief summary of RNS variants of some homomorphic encryptions. [ABSTRACT FROM AUTHOR]
- Published
- 2023
4. Power and area efficient FIR filter architecture in digital encephalography systems
- Author
-
Sudhanshu Janwadkar and Rasika Dhavse
- Subjects
Approximate arithmetic ,Approximate multipliers ,Biomedical signal processing ,Dadda tree multiplier ,Digital filter implementation ,Digital multipliers ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
In the process of Electroencephalogram (EEG) acquisition, the electrical signals from the brain are contaminated by numerous noise sources and artifacts. American Clinical Neurophysiology Society recommends digital filtering of acquired EEG signals with an upper cut-off frequency of 70 Hz before display in digital encephalography systems. We propose a linear symmetrical FIR filter architecture for filtering EEG signals using approximate computation techniques. Approximate computation techniques result in lower hardware resources and lower power consumption with some compromise in quality. Software tools used for this study include MATLAB (and its FDA tool) and Xilinx ISE 14.7. The chosen target platform is the Spartan-3e starter FPGA board. We propose the architecture for an Approximate Dadda Tree Multiplier. The proposed approximate multiplier consumes 25% lesser slices and 35.18% lower dynamic power than state-of-the-art approximate multipliers. The proposed FIR filter consumes 19.77% lesser LUTs and 34.97% lower power than state-of-the-art symmetric FIR filter architectures.
- Published
- 2023
- Full Text
- View/download PDF
5. Spatial Biases in Approximate Arithmetic Are Subject to Sequential Dependency Effects and Dissociate From Attentional Biases.
- Author
-
Glaser, Maria and Knops, André
- Subjects
MATH anxiety ,MATHEMATICAL ability ,COGNITIVE ability ,COGNITION ,SUBTRACTION (Mathematics) - Abstract
The notion that mental arithmetic is associated with shifts of spatial attention along a spatially organised mental number representation has received empirical support from three lines of research. First, participants tend to overestimate results of addition and underestimate those of subtraction problems in both exact and approximate formats. This has been termed the operational momentum (OM) effect. Second, participants are faster in detecting right-sided targets presented in the course of addition problems and left-sided targets in subtraction problems (attentional bias). Third, participants are biased toward choosing right-sided response alternatives to indicate the results of addition problems and left-sided response alternatives for subtraction problems (Spatial Association Of Responses [SOAR] effect). These effects potentially have their origin in operation-specific shifts of attention along a spatially organised mental number representation: rightward for addition and leftward for subtraction. Using a lateralised target detection task during the calculation phase of non-symbolic additions and subtractions, the current study measured the attentional focus, the OM and SOAR effects. In two experiments, we replicated the OM and SOAR effects but did not observe operation-spec ific biases in the lateralised target-detection task. We describe two new characteristics of the OM effect: First, a time-resolved, block-wise analysis of both experiments revealed sequential dependency effects in that the OM effect builds up over the course of the experiment, driven by the increasing underestimation of subtraction over time. Second, the OM effect was enhanced after arithmetic operation repetition compared to trials where arithmetic operation switched from one trial to the next. These results call into question the operation-specific attentional biases as the sole generator of the observed effects and point to the involvement of additional, potentially decisional processes that operate across trials. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
6. Interactive Proofs for Rounding Arithmetic
- Author
-
Shuo Chen, Jung Hee Cheon, Dongwoo Kim, and Daejun Park
- Subjects
Approximate arithmetic ,interactive proof ,verifiable computing ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
Interactive proofs are a type of verifiable computing that secures the integrity of computations. The need is increasing as more computations are outsourced to untrusted parties, e.g., cloud computing platforms. Existing techniques, however, have mainly focused on exact computations, but not approximate arithmetic (e.g., floating-point or fixed-point arithmetic). This makes it hard to apply them to certain types of computations (e.g., machine learning or financial applications) that inherently require approximate arithmetic. In this paper, we present an efficient interactive proof system for arithmetic circuits with rounding gates that can represent approximate arithmetic. The main idea is to reduce the rounding gate into a small sub-circuit without rounding, and reuse the machinery of the Goldwasser, Kalai, and Rothblum’s protocol (also known as the GKR protocol) and its recent refinements. Specifically, we shift the algebraic structure from a field to a ring to better deal with the notion of “digits”, and generalize the original GKR protocol over a ring. Then, we reduce the rounding operation to a low-degree polynomial over a ring, and develop a novel, optimal circuit construction of an arbitrary polynomial to transform the rounding polynomial to an optimal circuit representation. Moreover, further optimization on the proof generation cost for rounding is presented employing a Galois ring. Our experimental results show the efficiency of our protocol for approximate arithmetic, e.g., the implementation performed two orders of magnitude better than the existing system for a nested 128 by 128 matrix multiplication of depth 12 on the 16-bit fixed-point arithmetic.
- Published
- 2022
- Full Text
- View/download PDF
7. Young Children Intuitively Divide Before They Recognize the Division Symbol.
- Author
-
Szkudlarek, Emily, Zhang, Haobai, DeWind, Nicholas K., and Brannon, Elizabeth M.
- Subjects
NUMBER systems ,MATHEMATICAL ability ,ARITHMETIC ,INTELLECTUAL development ,NUMERALS - Abstract
Children bring intuitive arithmetic knowledge to the classroom before formal instruction in mathematics begins. For example, children can use their number sense to add, subtract, compare ratios, and even perform scaling operations that increase or decrease a set of dots by a factor of 2 or 4. However, it is currently unknown whether children can engage in a true division operation before formal mathematical instruction. Here we examined the ability of 6- to 9-year-old children and college students to perform symbolic and non-symbolic approximate division. Subjects were presented with non-symbolic (dot array) or symbolic (Arabic numeral) dividends ranging from 32 to 185, and non-symbolic divisors ranging from 2 to 8. Subjects compared their imagined quotient to a visible target quantity. Both children (Experiment 1 N = 89, Experiment 2 N = 42) and adults (Experiment 3 N = 87) were successful at the approximate division tasks in both dots and numeral formats. This was true even among the subset of children that could not recognize the division symbol or solve simple division equations, suggesting intuitive division ability precedes formal division instruction. For both children and adults, the ability to divide non-symbolically mediated the relation between Approximate Number System (ANS) acuity and symbolic math performance, suggesting that the ability to calculate non-symbolically may be a mechanism of the relation between ANS acuity and symbolic math. Our findings highlight the intuitive arithmetic abilities children possess before formal math instruction. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
8. Young Children Intuitively Divide Before They Recognize the Division Symbol
- Author
-
Emily Szkudlarek, Haobai Zhang, Nicholas K. DeWind, and Elizabeth M. Brannon
- Subjects
mathematical ability ,number sense ,division ,arithmetic ,approximate number system ,approximate arithmetic ,Neurosciences. Biological psychiatry. Neuropsychiatry ,RC321-571 - Abstract
Children bring intuitive arithmetic knowledge to the classroom before formal instruction in mathematics begins. For example, children can use their number sense to add, subtract, compare ratios, and even perform scaling operations that increase or decrease a set of dots by a factor of 2 or 4. However, it is currently unknown whether children can engage in a true division operation before formal mathematical instruction. Here we examined the ability of 6- to 9-year-old children and college students to perform symbolic and non-symbolic approximate division. Subjects were presented with non-symbolic (dot array) or symbolic (Arabic numeral) dividends ranging from 32 to 185, and non-symbolic divisors ranging from 2 to 8. Subjects compared their imagined quotient to a visible target quantity. Both children (Experiment 1 N = 89, Experiment 2 N = 42) and adults (Experiment 3 N = 87) were successful at the approximate division tasks in both dots and numeral formats. This was true even among the subset of children that could not recognize the division symbol or solve simple division equations, suggesting intuitive division ability precedes formal division instruction. For both children and adults, the ability to divide non-symbolically mediated the relation between Approximate Number System (ANS) acuity and symbolic math performance, suggesting that the ability to calculate non-symbolically may be a mechanism of the relation between ANS acuity and symbolic math. Our findings highlight the intuitive arithmetic abilities children possess before formal math instruction.
- Published
- 2022
- Full Text
- View/download PDF
9. Spatial Ability Explains the Male Advantage in Approximate Arithmetic
- Author
-
Wei, Wei, Chen, Chuansheng, and Zhou, Xinlin
- Subjects
Psychology ,Cognitive and Computational Psychology ,Applied and Developmental Psychology ,Basic Behavioral and Social Science ,Pediatric ,Behavioral and Social Science ,gender difference ,approximate arithmetic ,spatial ability ,Cognitive Sciences ,Biomedical and clinical sciences - Abstract
Previous research has shown that females consistently outperform males in exact arithmetic, perhaps due to the former's advantage in language processing. Much less is known about gender difference in approximate arithmetic. Given that approximate arithmetic is closely associated with visuospatial processing, which shows a male advantage we hypothesized that males would perform better than females in approximate arithmetic. In two experiments (496 children in Experiment 1 and 554 college students in Experiment 2), we found that males showed better performance in approximate arithmetic, which was accounted for by gender differences in spatial ability.
- Published
- 2016
10. A Full RNS Variant of Approximate Homomorphic Encryption
- Author
-
Cheon, Jung Hee, Han, Kyoohyung, Kim, Andrey, Kim, Miran, Song, Yongsoo, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Cid, Carlos, editor, and Jacobson Jr., Michael J., editor
- Published
- 2019
- Full Text
- View/download PDF
11. Design and Analysis of Approximate 4–2 Compressors for High-Accuracy Multipliers.
- Author
-
Kong, Tianqi and Li, Shuguo
- Subjects
COMPRESSORS ,VERY large scale circuit integration ,COMPRESSOR performance ,MATRIX multiplications - Abstract
Approximate multipliers are applicable in error-resilient applications with relaxed precision constraints, including image processing, multimedia, and data recognition. Such multipliers that sacrifice some accuracy can gain a corresponding increase in electrical performance. This article presents an analysis of the architectures of previously proposed compressors to investigate their performance and accuracy. In this article, we propose five high-accuracy approximate 4–2 compressors with better delay, area, power, and better performance–accuracy tradeoff. Pro1–Pro4 rely on the critical path optimization, while Pro5 derives from the modified sorting technique. This article implements $8 \times 8$ and $16 \times 16$ multipliers by employing the proposed approximate compressors in TSMC 28 nm. The experimental results indicate that our designs have about 18% delay, 43%–52% area-delay product (ADP) reduction compared to the exact multiplier, and 20%–55% ADP optimization compared to compressors with the same accuracy. This article further verifies the efficacy of the proposed compressors through image blending and matrix multiplication applications. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
12. Exact arithmetic, computational estimation and approximate arithmetic are different skills: Evidence from a study with 5‐year‐olds.
- Author
-
Sekeris, Elke, Verschaffel, Lieven, and Luwel, Koen
- Subjects
PROBLEM solving in children ,MEMORY ,COGNITION in children ,MATHEMATICS ,INTELLECT ,DESCRIPTIVE statistics ,SCHOOL children ,DATA analysis software - Abstract
Research distinguishes three types of arithmetic: exact arithmetic, computational estimation and approximate arithmetic. Little is, however, known about the interrelationship among these three arithmetic skills and the general cognitive and early numeracy skills that underlie these arithmetic skills. The current study investigates this interrelationship and underlying processes in 389 kindergartners. Exact arithmetic and computational estimation skills were assessed using a manipulative task, while approximate arithmetic was measured using a computerized task. Correlational analysis showed significant relations among the three arithmetic skills. At the same time, confirmatory factor analyses showed that they are different constructs. In addition, regression analysis showed that different general cognitive and early numeracy skills are predictive of the three arithmetic skills. Since the different arithmetic skills are related but distinct constructs and because they are driven by different processes, teaching and learning each of these skills ask for a different approach. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
13. Near-Optimal Polynomial for Modulus Reduction Using L2-Norm for Approximate Homomorphic Encryption
- Author
-
Yongwoo Lee, Joon-Woo Lee, Young-Sik Kim, and Jong-Seon No
- Subjects
Approximate arithmetic ,bootstrapping ,Cheon-Kim-Kim-Song (CKKS) scheme ,cryptography ,data privacy ,fully homomorphic encryption (FHE) ,Electrical engineering. Electronics. Nuclear engineering ,TK1-9971 - Abstract
Since Cheon et al. introduced an approximate homomorphic encryption scheme for complex numbers called Cheon-Kim-Kim-Song (CKKS) scheme, it has been widely used and applied in real-life situations, such as privacy-preserving machine learning. The polynomial approximation of a modulus reduction is the most difficult part of the bootstrapping for the CKKS scheme. In this article, we cast the problem of finding an approximate polynomial for a modulus reduction into an L2-norm minimization problem. As a result, we find an approximate polynomial for the modulus reduction without using the sine function, which is the upper bound for the approximation of the modulus reduction. With the proposed method, we can reduce the degree of the polynomial required for an approximate modulus reduction, while also reducing the error compared with the most recent result reported by Han et al. (CT-RSA’ 20). Consequently, we can achieve a low-error approximation, such that the maximum error is less than 2−40 for the size of the message $m/q\approx 2^{-10}$ . By using the proposed method, the constraint of $q = \mathcal {O}(m^{3/2})$ is relaxed as $\mathcal {O}(m)$ , and thus the level loss in bootstrapping can be reduced. The solution to the cast problem is determined in an efficient manner without iteration.
- Published
- 2020
- Full Text
- View/download PDF
14. Bootstrapping for Approximate Homomorphic Encryption
- Author
-
Cheon, Jung Hee, Han, Kyoohyung, Kim, Andrey, Kim, Miran, Song, Yongsoo, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Nielsen, Jesper Buus, editor, and Rijmen, Vincent, editor
- Published
- 2018
- Full Text
- View/download PDF
15. Homomorphic Encryption for Arithmetic of Approximate Numbers
- Author
-
Cheon, Jung Hee, Kim, Andrey, Kim, Miran, Song, Yongsoo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Takagi, Tsuyoshi, editor, and Peyrin, Thomas, editor
- Published
- 2017
- Full Text
- View/download PDF
16. Design space exploration for energy-efficient approximate Sobel filter.
- Author
-
Aoun, Alain, Masadeh, Mahmoud, and Tahar, Sofiène
- Subjects
- *
PARETO optimum , *IMAGE processing , *LIBRARY design & construction , *DIGITAL electronics , *ENERGY consumption , *DESIGN - Abstract
Approximate computing (AC) is an emerging computing paradigm for energy efficiency. AC is most suitable for error-tolerant applications, e.g., image processing. The Sobel filter is an edge detector which is used heavily in image processing. One of the basic blocks in the hardware implementation of the Sobel filter is the full adder (FA), which approximation can greatly reduce the energy consumption of the filter. In this paper, we propose three new Non-exact FAs (NeFAs) that are suitable for image processing. The proposed NeFAs along with existing approximate FAs are used to create a library of approximate FAs. We use this library to perform a design space exploration (DSE) of the approximate Sobel filter, which is an essential step when searching for an optimized implementation. Experiments have shown that the executed DSE was able to achieve a target reduction of up to 75% in area and power. We analyzed the generated designs objectively and subjectively. Using the subjective assessment, we defined two Pareto optimal criterion where we found that the implementations based on the proposed NeFA are in the Pareto optimal for high target reduction, i.e., most efficient designs. Based on the objective assessment, we found that the NeFA-based designs achieve outstanding quality and produce finer edges than the exact design in some cases. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
17. Homomorphic Comparison for Point Numbers with User-Controllable Precision and Its Applications
- Author
-
Heewon Chung, Myungsun Kim, Ahmad Al Badawi, Khin Mi Mi Aung, and Bharadwaj Veeravalli
- Subjects
(fully) homomorphic encryption ,continued fraction ,approximate arithmetic ,sorting ,Mathematics ,QA1-939 - Abstract
This work is mainly interested in ensuring users’ privacy in asymmetric computing, such as cloud computing. In particular, because lots of user data are expressed in non-integer data types, privacy-enhanced applications built on fully homomorphic encryption (FHE) must support real-valued comparisons due to the ubiquity of real numbers in real-world applications. However, as FHE schemes operate in specific domains, such as that of congruent integers, most FHE-based solutions focus only on homomorphic comparisons of integers. Attempts to overcome this barrier can be grouped into two classes. Given point numbers in the form of approximate real numbers, one class of solution uses a special-purpose encoding to represent the point numbers, whereas the other class constructs a dedicated FHE scheme to encrypt point numbers directly. The solutions in the former class may provide depth-efficient arithmetic (i.e., logarithmic depth in the size of the data), but not depth-efficient comparisons between FHE-encrypted point numbers. The second class may avoid this problem, but it requires the precision of point numbers to be determined before the FHE setup is run. Thus, the precision of the data cannot be controlled once the setup is complete. Furthermore, because the precision accuracy is closely related to the sizes of the encryption parameters, increasing the precision of point numbers results in increasing the sizes of the FHE parameters, which increases the sizes of the public keys and ciphertexts, incurring more expensive computation and storage. Unfortunately, this problem also occurs in many of the proposals that fall into the first class. In this work, we are interested in depth-efficient comparison over FHE-encrypted point numbers. In particular, we focus on enabling the precision of point numbers to be manipulated after the system parameters of the underlying FHE scheme are determined, and even after the point numbers are encrypted. To this end, we encode point numbers in continued fraction (CF) form. Therefore, our work lies in the first class of solutions, except that our CF-based approach allows depth-efficient homomorphic comparisons (more precisely, the complexity of the comparison is O ( log κ + log n ) for a number of partial quotients n and their bit length κ , which is normally small) while allowing users to determine the precision of the encrypted point numbers when running their applications. We develop several useful applications (e.g., sorting) that leverage our CF-based homomorphic comparisons.
- Published
- 2020
- Full Text
- View/download PDF
18. Testing the Efficacy of Training Basic Numerical Cognition and Transfer Effects to Improvement in Children’s Math Ability
- Author
-
Narae Kim, Selim Jang, and Soohyun Cho
- Subjects
approximate number sense ,training ,numerosity comparison ,numberline estimation ,approximate arithmetic ,symbol-to-numerosity mapping ,Psychology ,BF1-990 - Abstract
The goals of the present study were to test whether (and which) basic numerical abilities can be improved with training and whether training effects transfer to improvement in children’s math achievement. The literature is mixed with evidence that does or does not substantiate the efficacy of training basic numerical ability. In the present study, we developed a child-friendly software named “123 Bakery” which includes four training modules; non-symbolic numerosity comparison, non-symbolic numerosity estimation, approximate arithmetic, and symbol-to-numerosity mapping. Fifty-six first graders were randomly assigned to either the training or control group. The training group participated in 6 weeks of training (5 times a week, 30 minutes per day). All participants underwent pre- and post-training assessment of their basic numerical processing ability (including numerosity discrimination acuity, symbolic/non-symbolic magnitude estimation, approximate arithmetic, and symbol-to-numerosity mapping), overall math achievement and intelligence, 6 weeks apart. The acuity for numerosity discrimination (approximate number sense acuity; hereafter ANS acuity) significantly improved after training, but this training effect did not transfer to improvement in symbolic, exact calculation, or any other math ability. We conclude that basic numerical cognition training leads to improvement in ANS acuity, but whether this effect transfers to symbolic math ability remains to be further tested.
- Published
- 2018
- Full Text
- View/download PDF
19. Approximate Arithmetic Training Improves Informal Math Performance in Low Achieving Preschoolers
- Author
-
Emily Szkudlarek and Elizabeth M. Brannon
- Subjects
preschool math ,approximate number system ,cognitive training ,approximate arithmetic ,numerical cognition ,tablet application ,Psychology ,BF1-990 - Abstract
Recent studies suggest that practice with approximate and non-symbolic arithmetic problems improves the math performance of adults, school aged children, and preschoolers. However, the relative effectiveness of approximate arithmetic training compared to available educational games, and the type of math skills that approximate arithmetic targets are unknown. The present study was designed to (1) compare the effectiveness of approximate arithmetic training to two commercially available numeral and letter identification tablet applications and (2) to examine the specific type of math skills that benefit from approximate arithmetic training. Preschool children (n = 158) were pseudo-randomly assigned to one of three conditions: approximate arithmetic, letter identification, or numeral identification. All children were trained for 10 short sessions and given pre and post tests of informal and formal math, executive function, short term memory, vocabulary, alphabet knowledge, and number word knowledge. We found a significant interaction between initial math performance and training condition, such that children with low pretest math performance benefited from approximate arithmetic training, and children with high pretest math performance benefited from symbol identification training. This effect was restricted to informal, and not formal, math problems. There were also effects of gender, socio-economic status, and age on post-test informal math score after intervention. A median split on pretest math ability indicated that children in the low half of math scores in the approximate arithmetic training condition performed significantly better than children in the letter identification training condition on post-test informal math problems when controlling for pretest, age, gender, and socio-economic status. Our results support the conclusion that approximate arithmetic training may be especially effective for children with low math skills, and that approximate arithmetic training improves early informal, but not formal, math skills.
- Published
- 2018
- Full Text
- View/download PDF
20. Design Space Exploration on High-Order QAM Demodulation Circuits: Algorithms, Arithmetic and Approximation Techniques
- Author
-
Ioannis Stratakos, Vasileios Leon, Giorgos Armeniakos, George Lentaris, and Dimitrios Soudris
- Subjects
QAM demodulation ,approximate computing ,approximate arithmetic ,FPGA ,design space exploration ,log likelihood ratio ,maximum likelihood ,TK7800-8360 ,Computer Networks and Communications ,020206 networking & telecommunications ,02 engineering and technology ,020202 computer hardware & architecture ,Hardware and Architecture ,Control and Systems Engineering ,Signal Processing ,0202 electrical engineering, electronic engineering, information engineering ,Electrical and Electronic Engineering ,Electronics - Abstract
Every new generation of wireless communication standard aims to improve the overall performance and quality of service (QoS), compared to the previous generations. Increased data rates, numbers and capabilities of connected devices, new applications, and higher data volume transfers are some of the key parameters that are of interest. To satisfy these increased requirements, the synergy between wireless technologies and optical transport will dominate the 5G network topologies. This work focuses on a fundamental digital function in an orthogonal frequency-division multiplexing (OFDM) baseband transceiver architecture and aims at improving the throughput and circuit complexity of this function. Specifically, we consider the high-order QAM demodulation and apply approximation techniques to achieve our goals. We adopt approximate computing as a design strategy to exploit the error resiliency of the QAM function and deliver significant gains in terms of critical performance metrics. Particularly, we take into consideration and explore four demodulation algorithms and develop accurate floating- and fixed-point circuits in VHDL. In addition, we further explore the effects of introducing approximate arithmetic components. For our test case, we consider 64-QAM demodulators, and the results suggest that the most promising design provides bit error rates (BER) ranging from 10−1 to 10−4 for SNR 0–14 dB in terms of accuracy. Targeting a Xilinx Zynq Ultrascale+ ZCU106 (XCZU7EV) FPGA device, the approximate circuits achieve up to 98% reduction in LUT utilization, compared to the accurate floating-point model of the same algorithm, and up to a 122% increase in operating frequency. In terms of power consumption, our most efficient circuit configurations consume 0.6–1.1 W when operating at their maximum clock frequency. Our results show that if the objective is to achieve high accuracy in terms of BER, the prevailing solution is the approximate LLR algorithm configured with fixed-point arithmetic and 8-bit truncation, providing 81% decrease in LUTs and 13% increase in frequency and sustains a throughput of 323 Msamples/s.
- Published
- 2022
21. Approximate Arithmetic Training Improves Informal Math Performance in Low Achieving Preschoolers.
- Author
-
Szkudlarek, Emily and Brannon, Elizabeth M.
- Subjects
PSYCHOLOGY of preschool children ,COGNITIVE training ,ARITHMETIC education in preschools ,PERFORMANCE evaluation ,PROBLEM solving - Published
- 2018
- Full Text
- View/download PDF
22. A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration.
- Author
-
Becker, Ruben, Sagraloff, Michael, Sharma, Vikram, and Yap, Chee
- Subjects
- *
ITERATIVE methods (Mathematics) , *ALGORITHMS , *QUADTREES , *APPROXIMATION theory , *MATHEMATICAL bounds , *COMPUTATIONAL complexity - Abstract
We describe a subdivision algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F , our algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem , namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ , our algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
23. Logarithmic Arithmetic for Low-Power Adaptive Control Systems.
- Author
-
Lotrič, Uroš and Bulić, Patricio
- Subjects
- *
ENERGY dissipation , *ARITHMETIC , *KALMAN filtering , *RADAR , *AERONAUTICS - Abstract
To reduce the power dissipation in adaptive control systems, we propose replacing the exact arithmetic hardware units with approximate ones. As a case study, an adaptive control system for object tracking based on the Kalman filter is implemented in FPGA. A thorough analysis of the Kalman filter's circuitry for real-world object tracks acquired by an aviation radar system proved that adaptive control systems can successfully compensate for the calculation errors introduced by the approximate arithmetic units. The main contributions of this paper are that the introduction of the approximate arithmetic circuits to the adaptive control system (1) preserves the required accuracy and (2) significantly reduces the power dissipation and the size of the adaptive system's circuitry. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
24. Grid-Based Histogram Arithmetic for the Probabilistic Analysis of Functions
- Author
-
Carreras, Carlos, Hermenegildo, Manuel V., Goos, G., editor, Hartmanis, J., editor, van Leeuwen, J., editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Choueiry, Berthe Y., editor, and Walsh, Toby, editor
- Published
- 2000
- Full Text
- View/download PDF
25. A High-Performance and Energy-Efficient FIR Adaptive Filter Using Approximate Distributed Arithmetic Circuits.
- Author
-
Jiang, Honglan, Liu, Leibo, Jonker, Pieter P., Elliott, Duncan G., Lombardi, Fabrizio, and Han, Jie
- Subjects
- *
ADAPTIVE filters , *ENERGY consumption , *ALGORITHMS - Abstract
In this paper, a fixed-point finite impulse response adaptive filter is proposed using approximate distributed arithmetic (DA) circuits. In this design, the radix-8 Booth algorithm is used to reduce the number of partial products in the DA architecture, although no multiplication is explicitly performed. In addition, the partial products are approximately generated by truncating the input data with an error compensation. To further reduce hardware costs, an approximate Wallace tree is considered for the accumulation of partial products. As a result, the delay, area, and power consumption of the proposed design are significantly reduced. The application of system identification using a 48-tap bandpass filter and a 103-tap high-pass filter shows that the approximate design achieves a similar accuracy as its accurate counterpart. Compared with the state-of-the-art adaptive filter using bit-level pruning in the adder tree (referred to as the delayed least mean square (DLMS) design), it has a lower steady-state mean squared error and a smaller normalized misalignment. Synthesis results show that the proposed design attains on average a 55% reduction in energy per operation (EPO) and a $3.2\times $ throughput per area compared with an accurate design. Moreover, the proposed design achieves 45%–61% lower EPO compared with the DLMS design. A saccadic system using the proposed approximate adaptive filter-based cerebellar model achieves a similar retinal slip as using an accurate filter. These results are promising for the large-scale integration of approximate circuits into high-performance and energy-efficient systems for error-resilient applications. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
26. Computing real roots of real polynomials.
- Author
-
Sagraloff, Michael and Mehlhorn, Kurt
- Subjects
- *
POLYNOMIALS , *COMPUTER science , *FACTORIZATION , *APPROXIMATION theory , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 2 In Victor Pan's own words: “Our algorithms are quite involved, and their implementation would require a non-trivial work, incorporating numerous known implementation techniques and tricks”. In fact, we are not aware of any implementation of Pan's method. and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted A New Dsc , which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. A New Dsc can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
27. Accuracy-Configurable Adder for Approximate Arithmetic Designs.
- Author
-
Kahng, Andrew B. and Seokhyeong Kang
- Subjects
ENERGY consumption ,PERFORMANCE ,ADAPTIVE computing systems ,QUALITY ,SET theory - Abstract
Approximation can increase performance or reduce power consumption with a simplified or inaccurate circuit in application contexts where strict requirements are relaxed. For applications related to human senses, approximate arithmetic can be used to generate sufficient results rather than absolutely accurate results. Approximate design exploits a tradeoff of accuracy in computation versus performance and power. However, required accuracy varies according to applications, and 100% accurate results are still required in some situations. In this paper, we propose an accuracy-configurable approximate (ACA) adder for which the accuracy of results is configurable during runtime. Because of its configurability, the ACA adder can adaptively operate in both approximate (inaccurate) mode and accurate mode. The proposed adder can achieve significant throughput improvement and total power reduction over conventional adder designs. It can be used in accuracy-configurable applications, and improves the achievable tradeoff between performance/ power and quality. The ACA adder achieves approximately 30% power reduction versus the conventional pipelined adder at the relaxed accuracy requirement. [ABSTRACT FROM AUTHOR]
- Published
- 2012
28. Approximate Floating-Point Operations with Integer Units by Processing in the Logarithmic Domain
- Author
-
Noah Hellman and Oscar Gustafsson
- Subjects
Floating point ,Approximate arithmetic ,Floating-point ,Multiplication ,Division ,Square-root ,Logarithm ,Approximation algorithm ,Division (mathematics) ,Domain (mathematical analysis) ,Datorsystem ,Computer Systems ,Inbäddad systemteknik ,Hardware_ARITHMETICANDLOGICSTRUCTURES ,Arithmetic ,Constant (mathematics) ,Embedded Systems ,Integer (computer science) ,Mathematics - Abstract
Floating-point numbers represented using a hidden one can readily be approximately converted to the logarithmic domain using Mitchell's approximation. Once in the logarithmic domain, several arithmetic operations including multiplication, division, and square-root can be easily computed using the integer arithmetic unit. This has earlier been used in fast reciprocal square-root algorithms, sometimes referred to as magic number algorithms. The proposed approximate operations are realized by performing an integer operation using an integer unit on floating-point data and adding an integer constant to obtain the approximate floating-point result. In this work, we derive easy to use equations and constants for multiple floating-point formats and operations.
- Published
- 2021
29. Improving arithmetic performance with number sense training: An investigation of underlying mechanism.
- Author
-
Park, Joonkoo and Brannon, Elizabeth M.
- Subjects
- *
ARITHMETIC , *APPROXIMATION theory , *TASK performance , *NUMERICAL analysis , *PSYCHOLOGY of adults , *MATHEMATICS education - Abstract
A nonverbal primitive number sense allows approximate estimation and mental manipulations on numerical quantities without the use of numerical symbols. In a recent randomized controlled intervention study in adults, we demonstrated that repeated training on a non-symbolic approximate arithmetic task resulted in improved exact symbolic arithmetic performance, suggesting a causal relationship between the primitive number sense and arithmetic competence. Here, we investigate the potential mechanisms underlying this causal relationship. We constructed multiple training conditions designed to isolate distinct cognitive components of the approximate arithmetic task. We then assessed the effectiveness of these training conditions in improving exact symbolic arithmetic in adults. We found that training on approximate arithmetic, but not on numerical comparison, numerical matching, or visuo-spatial short-term memory, improves symbolic arithmetic performance. In addition, a second experiment revealed that our approximate arithmetic task does not require verbal encoding of number, ruling out an alternative explanation that participants use exact symbolic strategies during approximate arithmetic training. Based on these results, we propose that nonverbal numerical quantity manipulation is one key factor that drives the link between the primitive number sense and symbolic arithmetic competence. Future work should investigate whether training young children on approximate arithmetic tasks even before they solidify their symbolic number understanding is fruitful for improving readiness for math education. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
30. Failure to replicate the benefit of approximate arithmetic training for symbolic arithmetic fluency in adults
- Author
-
Joonkoo Park, Elizabeth M. Brannon, and Emily Szkudlarek
- Subjects
Adult ,Linguistics and Language ,Cognitive Neuroscience ,Numerical cognition ,Math ,Replication ,Experimental and Cognitive Psychology ,050105 experimental psychology ,Language and Linguistics ,Article ,03 medical and health sciences ,Fluency ,0302 clinical medicine ,Cognition ,Developmental and Educational Psychology ,Approximate number system ,Humans ,0501 psychology and cognitive sciences ,Arithmetic ,Approximate arithmetic ,Working memory ,05 social sciences ,Subtraction ,Training effect ,Cognitive training ,Memory, Short-Term ,Sample size determination ,Psychology ,030217 neurology & neurosurgery ,Mathematics - Abstract
Previous research reported that college students' symbolic addition and subtraction fluency improved after training with non-symbolic, approximate addition and subtraction. These findings were widely interpreted as strong support for the hypothesis that the Approximate Number System (ANS) plays a causal role in symbolic mathematics, and that this relation holds into adulthood. Here we report four experiments that fail to find evidence for this causal relation. Experiment 1 examined whether the approximate arithmetic training effect exists within a shorter training period than originally reported (2 vs 6 days of training). Experiment 2 attempted to replicate and compare the approximate arithmetic training effect to a control training condition matched in working memory load. Experiments 3 and 4 replicated the original approximate arithmetic training experiments with a larger sample size. Across all four experiments (N = 318) approximate arithmetic training was no more effective at improving the arithmetic fluency of adults than training with control tasks. Results call into question any causal relationship between approximate, non-symbolic arithmetic and precise symbolic arithmetic.
- Published
- 2020
31. A High-Performance and Energy-Efficient FIR Adaptive Filter Using Approximate Distributed Arithmetic Circuits
- Author
-
Fabrizio Lombardi, Duncan G. Elliott, Honglan Jiang, Jie Han, Leibo Liu, and Pieter Jonker
- Subjects
Adaptive filter ,Adder ,truncation ,Finite impulse response ,020208 electrical & electronic engineering ,02 engineering and technology ,radix-8 Booth algorithm ,approximate arithmetic ,Wallace tree ,020202 computer hardware & architecture ,Least mean squares filter ,Band-pass filter ,Hardware and Architecture ,Filter (video) ,distributed arithmetic ,0202 electrical engineering, electronic engineering, information engineering ,Booth's multiplication algorithm ,Electrical and Electronic Engineering ,Algorithm ,Mathematics - Abstract
In this paper, a fixed-point finite impulse response adaptive filter is proposed using approximate distributed arithmetic (DA) circuits. In this design, the radix-8 Booth algorithm is used to reduce the number of partial products in the DA architecture, although no multiplication is explicitly performed. In addition, the partial products are approximately generated by truncating the input data with an error compensation. To further reduce hardware costs, an approximate Wallace tree is considered for the accumulation of partial products. As a result, the delay, area, and power consumption of the proposed design are significantly reduced. The application of system identification using a 48-tap bandpass filter and a 103-tap high-pass filter shows that the approximate design achieves a similar accuracy as its accurate counterpart. Compared with the state-of-the-art adaptive filter using bit-level pruning in the adder tree (referred to as the delayed least mean square (DLMS) design), it has a lower steady-state mean squared error and a smaller normalized misalignment. Synthesis results show that the proposed design attains on average a 55% reduction in energy per operation (EPO) and a $3.2\times $ throughput per area compared with an accurate design. Moreover, the proposed design achieves 45%–61% lower EPO compared with the DLMS design. A saccadic system using the proposed approximate adaptive filter-based cerebellar model achieves a similar retinal slip as using an accurate filter. These results are promising for the large-scale integration of approximate circuits into high-performance and energy-efficient systems for error-resilient applications.
- Published
- 2019
- Full Text
- View/download PDF
32. Working Memory in Nonsymbolic Approximate Arithmetic Processing: A Dual-Task Study With Preschoolers.
- Author
-
Xenidou‐Dervou, Iro, Lieshout, Ernest C. D. M., and Schoot, Menno
- Subjects
- *
SHORT-term memory , *ARITHMETIC series , *TASK performance , *PRESCHOOL children , *EMOTIONS & cognition - Abstract
Preschool children have been proven to possess nonsymbolic approximate arithmetic skills before learning how to manipulate symbolic math and thus before any formal math instruction. It has been assumed that nonsymbolic approximate math tasks necessitate the allocation of Working Memory (WM) resources. WM has been consistently shown to be an important predictor of children's math development and achievement. The aim of our study was to uncover the specific role of WM in nonsymbolic approximate math. For this purpose, we conducted a dual-task study with preschoolers with active phonological, visual, spatial, and central executive interference during the completion of a nonsymbolic approximate addition dot task. With regard to the role of WM, we found a clear performance breakdown in the central executive interference condition. Our findings provide insight into the underlying cognitive processes involved in storing and manipulating nonsymbolic approximate numerosities during early arithmetic. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
33. Design Space Exploration on High-Order QAM Demodulation Circuits: Algorithms, Arithmetic and Approximation Techniques †.
- Author
-
Stratakos, Ioannis, Leon, Vasileios, Armeniakos, Giorgos, Lentaris, George, and Soudris, Dimitrios
- Subjects
DEMODULATION ,CIRCUIT complexity ,ARITHMETIC ,BIT error rate ,ORTHOGONAL functions ,5G networks - Abstract
Every new generation of wireless communication standard aims to improve the overall performance and quality of service (QoS), compared to the previous generations. Increased data rates, numbers and capabilities of connected devices, new applications, and higher data volume transfers are some of the key parameters that are of interest. To satisfy these increased requirements, the synergy between wireless technologies and optical transport will dominate the 5G network topologies. This work focuses on a fundamental digital function in an orthogonal frequency-division multiplexing (OFDM) baseband transceiver architecture and aims at improving the throughput and circuit complexity of this function. Specifically, we consider the high-order QAM demodulation and apply approximation techniques to achieve our goals. We adopt approximate computing as a design strategy to exploit the error resiliency of the QAM function and deliver significant gains in terms of critical performance metrics. Particularly, we take into consideration and explore four demodulation algorithms and develop accurate floating- and fixed-point circuits in VHDL. In addition, we further explore the effects of introducing approximate arithmetic components. For our test case, we consider 64-QAM demodulators, and the results suggest that the most promising design provides bit error rates (BER) ranging from 10 − 1 to 10 − 4 for SNR 0–14 dB in terms of accuracy. Targeting a Xilinx Zynq Ultrascale+ ZCU106 (XCZU7EV) FPGA device, the approximate circuits achieve up to 98 % reduction in LUT utilization, compared to the accurate floating-point model of the same algorithm, and up to a 122 % increase in operating frequency. In terms of power consumption, our most efficient circuit configurations consume 0.6–1.1 W when operating at their maximum clock frequency. Our results show that if the objective is to achieve high accuracy in terms of BER, the prevailing solution is the approximate LLR algorithm configured with fixed-point arithmetic and 8-bit truncation, providing 81 % decrease in LUTs and 13 % increase in frequency and sustains a throughput of 323 Msamples/s. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
34. A high-performance and energy-efficient FIR adaptive filter using approximate distributed arithmetic circuits
- Author
-
Jiang, Honglan (author), Liu, Leibo (author), Jonker, P.P. (author), Elliott, Duncan G. (author), Lombardi, Fabrizio (author), Han, Jie (author), Jiang, Honglan (author), Liu, Leibo (author), Jonker, P.P. (author), Elliott, Duncan G. (author), Lombardi, Fabrizio (author), and Han, Jie (author)
- Abstract
In this paper, a fixed-point finite impulse response adaptive filter is proposed using approximate distributed arithmetic (DA) circuits. In this design, the radix-8 Booth algorithm is used to reduce the number of partial products in the DA architecture, although no multiplication is explicitly performed. In addition, the partial products are approximately generated by truncating the input data with an error compensation. To further reduce hardware costs, an approximate Wallace tree is considered for the accumulation of partial products. As a result, the delay, area, and power consumption of the proposed design are significantly reduced. The application of system identification using a 48-Tap bandpass filter and a 103-Tap high-pass filter shows that the approximate design achieves a similar accuracy as its accurate counterpart. Compared with the state-of-The-Art adaptive filter using bit-level pruning in the adder tree (referred to as the delayed least mean square (DLMS) design), it has a lower steady-state mean squared error and a smaller normalized misalignment. Synthesis results show that the proposed design attains on average a 55% reduction in energy per operation (EPO) and a 3.2\times throughput per area compared with an accurate design. Moreover, the proposed design achieves 45%-61% lower EPO compared with the DLMS design. A saccadic system using the proposed approximate adaptive filter-based cerebellar model achieves a similar retinal slip as using an accurate filter. These results are promising for the large-scale integration of approximate circuits into high-performance and energy-efficient systems for error-resilient applications., Accepted Author Manuscript, Biomechatronics & Human-Machine Control
- Published
- 2019
- Full Text
- View/download PDF
35. Constructing strongly convex hulls using exact or rounded arithmetic.
- Author
-
Li, Zhenyu and Milenkovic, Victor
- Abstract
One useful generalization of the convex hull of a set S of n points is the ɛ- strongly convex δ- hull. It is defined to be a convex polygon with vertices taken from S such that no point in S lies farther than δ outside and such that even if the vertices of are perturbed by as much as ɛ, remains convex. It was an open question as to whether an ɛ-strongly convex O(ɛ)-hull existed for all positive ɛ. We give here an O( n log n) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an ɛ-strongly convex O(ɛ + μ)-hull in O( n log n) time using rounded arithmetic with rounding unit μ. This is the first rounded-arithmetic convex-hull algorithm which guarantees a convex output and which has error independent of n. [ABSTRACT FROM AUTHOR]
- Published
- 1992
- Full Text
- View/download PDF
36. Approximate Fixed-Point Elementary Function Accelerator for the SpiNNaker-2 Neuromorphic Chip
- Author
-
Gengting Liu, David Lester, Mantas Mikaitis, Stefan Scholze, Steve Furber, Sebastian Hoppner, Delong Shang, Jim Garside, and Andreas Dixius
- Subjects
Adder ,Computer science ,fixed-point arithmetic ,020208 electrical & electronic engineering ,exponential function ,02 engineering and technology ,MPSoC ,hardware accelerators ,approximate arithmetic ,Chip ,neuromorphic computing ,Computational science ,Exponential function ,logarithm function ,Computer Science::Hardware Architecture ,03 medical and health sciences ,0302 clinical medicine ,Neuromorphic engineering ,0202 electrical engineering, electronic engineering, information engineering ,SpiNNaker2 ,Hardware acceleration ,Elementary function ,Fixed-point arithmetic ,030217 neurology & neurosurgery - Abstract
Neuromorphic chips are used to model biologically inspired Spiking-Neural-Networks(SNNs) where most models are based on differential equations. Equations for most SNN algorithms usually contain variables with one or more $e^{x}$ components. SpiNNaker is a digital neuromorphic chip that has so far been using pre-calculated look-up tables for exponential function. However this approach is limited because the memory requirements grow as more complex neural models are developed. To save already limited memory resources in the next generation SpiNNaker chip, we are including a fast exponential function in the silicon. In this paper we analyse iterative algorithms for elementary functions and show how to build a single hardware accelerator for exp and natural log, for a neuromorphic chip prototype, to be manufactured in a 22 nm FDSOI process. We present the accelerator that has algorithmic level approximation control, allowing it to trade precision for latency and energy efficiency. As an addition to neuromorphic chip application, we provide analysis of a parameterized elementary function unit that can be tailored for other systems with different power, area, accuracy and latency constraints.
- Published
- 2018
- Full Text
- View/download PDF
37. Approximate Arithmetic Training Improves Informal Math Performance in Low Achieving Preschoolers
- Author
-
Elizabeth M. Brannon and Emily Szkudlarek
- Subjects
Vocabulary ,media_common.quotation_subject ,education ,lcsh:BF1-990 ,Numerical cognition ,Short-term memory ,preschool math ,approximate arithmetic ,behavioral disciplines and activities ,tablet application ,050105 experimental psychology ,Numeral system ,cognitive training ,mental disorders ,Approximate number system ,Psychology ,0501 psychology and cognitive sciences ,Arithmetic ,numerical cognition ,General Psychology ,media_common ,Original Research ,approximate number system ,4. Education ,05 social sciences ,Cognitive training ,Identification (information) ,lcsh:Psychology ,Symbol (formal) ,psychological phenomena and processes ,050104 developmental & child psychology - Abstract
Recent studies suggest that practice with approximate and non-symbolic arithmetic problems improves the math performance of adults, school aged children, and preschoolers. However, the relative effectiveness of approximate arithmetic training compared to available educational games, and the type of math skills that approximate arithmetic targets are unknown. The present study was designed to (1) compare the effectiveness of approximate arithmetic training to two commercially available numeral and letter identification tablet applications and (2) to examine the specific type of math skills that benefit from approximate arithmetic training. Preschool children (n = 158) were pseudo-randomly assigned to one of three conditions: approximate arithmetic, letter identification, or numeral identification. All children were trained for 10 short sessions and given pre and post tests of informal and formal math, executive function, short term memory, vocabulary, alphabet knowledge, and number word knowledge. We found a significant interaction between initial math performance and training condition, such that children with low pretest math performance benefited from approximate arithmetic training, and children with high pretest math performance benefited from symbol identification training. This effect was restricted to informal, and not formal, math problems. There were also effects of gender, socio-economic status, and age on post-test informal math score after intervention. A median split on pretest math ability indicated that children in the low half of math scores in the approximate arithmetic training condition performed significantly better than children in the letter identification training condition on post-test informal math problems when controlling for pretest, age, gender, and socio-economic status. Our results support the conclusion that approximate arithmetic training may be especially effective for children with low math skills, and that approximate arithmetic training improves early informal, but not formal, math skills.
- Published
- 2018
- Full Text
- View/download PDF
38. Failure to replicate the benefit of approximate arithmetic training for symbolic arithmetic fluency in adults.
- Author
-
Szkudlarek, Emily, Park, Joonkoo, and Brannon, Elizabeth M.
- Subjects
- *
ARITHMETIC , *NUMBER systems , *MENTAL arithmetic , *SHORT-term memory , *ADULTS , *VISUAL memory , *SAMPLE size (Statistics) , *COGNITION , *MATHEMATICS , *RESEARCH funding - Abstract
Previous research reported that college students' symbolic addition and subtraction fluency improved after training with non-symbolic, approximate addition and subtraction. These findings were widely interpreted as strong support for the hypothesis that the Approximate Number System (ANS) plays a causal role in symbolic mathematics, and that this relation holds into adulthood. Here we report four experiments that fail to find evidence for this causal relation. Experiment 1 examined whether the approximate arithmetic training effect exists within a shorter training period than originally reported (2 vs 6 days of training). Experiment 2 attempted to replicate and compare the approximate arithmetic training effect to a control training condition matched in working memory load. Experiments 3 and 4 replicated the original approximate arithmetic training experiments with a larger sample size. Across all four experiments (N = 318) approximate arithmetic training was no more effective at improving the arithmetic fluency of adults than training with control tasks. Results call into question any causal relationship between approximate, non-symbolic arithmetic and precise symbolic arithmetic. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
39. Approximate Arithmetic Abilities in Childhood
- Author
-
Gilmore, Camilla, Cohen Kadosh, Roi, book editor, and Dowker, Ann, book editor
- Published
- 2015
- Full Text
- View/download PDF
40. Homomorphic Comparison for Point Numbers with User-Controllable Precision and Its Applications.
- Author
-
Chung, Heewon, Kim, Myungsun, Badawi, Ahmad Al, Aung, Khin Mi Mi, and Veeravalli, Bharadwaj
- Subjects
REAL numbers ,CONTINUED fractions ,CLOUD computing - Abstract
This work is mainly interested in ensuring users' privacy in asymmetric computing, such as cloud computing. In particular, because lots of user data are expressed in non-integer data types, privacy-enhanced applications built on fully homomorphic encryption (FHE) must support real-valued comparisons due to the ubiquity of real numbers in real-world applications. However, as FHE schemes operate in specific domains, such as that of congruent integers, most FHE-based solutions focus only on homomorphic comparisons of integers. Attempts to overcome this barrier can be grouped into two classes. Given point numbers in the form of approximate real numbers, one class of solution uses a special-purpose encoding to represent the point numbers, whereas the other class constructs a dedicated FHE scheme to encrypt point numbers directly. The solutions in the former class may provide depth-efficient arithmetic (i.e., logarithmic depth in the size of the data), but not depth-efficient comparisons between FHE-encrypted point numbers. The second class may avoid this problem, but it requires the precision of point numbers to be determined before the FHE setup is run. Thus, the precision of the data cannot be controlled once the setup is complete. Furthermore, because the precision accuracy is closely related to the sizes of the encryption parameters, increasing the precision of point numbers results in increasing the sizes of the FHE parameters, which increases the sizes of the public keys and ciphertexts, incurring more expensive computation and storage. Unfortunately, this problem also occurs in many of the proposals that fall into the first class. In this work, we are interested in depth-efficient comparison over FHE-encrypted point numbers. In particular, we focus on enabling the precision of point numbers to be manipulated after the system parameters of the underlying FHE scheme are determined, and even after the point numbers are encrypted. To this end, we encode point numbers in continued fraction (CF) form. Therefore, our work lies in the first class of solutions, except that our CF-based approach allows depth-efficient homomorphic comparisons (more precisely, the complexity of the comparison is O (log κ + log n) for a number of partial quotients n and their bit length κ , which is normally small) while allowing users to determine the precision of the encrypted point numbers when running their applications. We develop several useful applications (e.g., sorting) that leverage our CF-based homomorphic comparisons. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
41. Computing Real Roots of Real Polynomials ... and now For Real!
- Author
-
Michael Sagraloff, Alexander Kobel, Fabrice Rouillier, Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft, OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Université Pierre et Marie Curie - Paris 6 (UPMC)
- Subjects
Computer Science - Symbolic Computation ,G.4 ,FOS: Computer and information sciences ,Polynomial ,G.1.5 ,Newton’s method ,010103 numerical & computational mathematics ,Symbolic Computation (cs.SC) ,approximate arithmetic ,01 natural sciences ,G.1.0 ,certified computation ,symbols.namesake ,univariate polynomials ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,FOS: Mathematics ,Descartes' rule of signs ,Overhead (computing) ,Mathematics - Numerical Analysis ,0101 mathematics ,Newton's method ,Subdivision ,Mathematics ,Descartes method ,real roots ,[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] ,business.industry ,010102 general mathematics ,Computer Science - Numerical Analysis ,root finding ,Numerical Analysis (math.NA) ,Solver ,65H04, 68N30 (Primary) 68W30 (Secondary) ,Symbolic computation ,root iso- lation ,symbols ,Computer Science - Mathematical Software ,business ,Mathematical Software (cs.MS) ,Root-finding algorithm ,Algorithm - Abstract
Very recent work introduces an asymptotically fast subdivision algorithm, denoted ANewDsc, for isolating the real roots of a univariate real polynomial. The method combines Descartes' Rule of Signs to test intervals for the existence of roots, Newton iteration to speed up convergence against clusters of roots, and approximate computation to decrease the required precision. It achieves record bounds on the worst-case complexity for the considered problem, matching the complexity of Pan's method for computing all complex roots and improving upon the complexity of other subdivision methods by several magnitudes. In the article at hand, we report on an implementation of ANewDsc on top of the RS root isolator. RS is a highly efficient realization of the classical Descartes method and currently serves as the default real root solver in Maple. We describe crucial design changes within ANewDsc and RS that led to a high-performance implementation without harming the theoretical complexity of the underlying algorithm. With an excerpt of our extensive collection of benchmarks, available online at http://anewdsc.mpi-inf.mpg.de/, we illustrate that the theoretical gain in performance of ANewDsc over other subdivision methods also transfers into practice. These experiments also show that our new implementation outperforms both RS and mature competitors by magnitudes for notoriously hard instances with clustered roots. For all other instances, we avoid almost any overhead by integrating additional optimizations and heuristics., Comment: Accepted for presentation at the 41st International Symposium on Symbolic and Algebraic Computation (ISSAC), July 19--22, 2016, Waterloo, Ontario, Canada
- Published
- 2016
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.