English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Given an array $X$ of $N+1$ strictly ordered floating point numbers and afloating point number $z$ in the interval $[X_0,X_N)$, a common problem is tofind the index $i$ of the interval $[X_{i},X_{i+1})$ containing $z$. Thisproblem arises for instance in the context of spline interpolation or thecomputation of empirical probability distribution from empirical data. Often itneeds to be solved for a large number of different values $z$ and the samearray $X$, which makes it worth investing resources upfront in pre-processingthe array $X$ with the goal of speeding up subsequent search operations. Insome cases the values $z$ to be processed are known simultaneously in blocks ofsize $M$, which offers the opportunity to solve the problem vectorially,exploiting the parallel capabilities of modern CPUs. The common solution is tosequentially invoke $M$ times the well known binary search algorithm, which hascomplexity $O(log_2 N)$ per individual search and, in its classic formulation,is not vectorizable, i.e. is not SIMD friendly. This paper describes technicalimprovements to the binary search algorithm, which make it faster andvectorizable. Next it proposes a new vectorizable algorithm, based on anindexing technique, applicable to a wide family of $X$ partitions, which solvesthe problem with complexity $O(1)$ per individual search at the cost ofintroducing an initial overhead to compute the index and requiring extra memoryfor its storage. Test results using streaming SIMD extensions compare theperformance of the algorithm versus various benchmarks and demonstrate itseffectiveness. Depending on the test case, the algorithm can produce athroughput up to two orders of magnitude larger than the classic binary search.Applicability limitations and cache-friendliness related aspects are alsodiscussed.

Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers