{"id":1049,"date":"2022-05-29T20:48:35","date_gmt":"2022-05-30T00:48:35","guid":{"rendered":"https:\/\/jausoft.com\/blog\/?p=1049"},"modified":"2022-05-30T02:39:00","modified_gmt":"2022-05-30T06:39:00","slug":"rational-expression-with-frictionless-fractions-and-implemented-time-in-cpp","status":"publish","type":"post","link":"https:\/\/jausoft.com\/blog\/2022\/05\/29\/rational-expression-with-frictionless-fractions-and-implemented-time-in-cpp\/","title":{"rendered":"Rational Expressions with frictionless Fractions and implemented Time"},"content":{"rendered":"

Natural numbers are defined as the sequence of numbers fully defined by their initial value, <\/em>its successor and the successor of its successor and so forth. Despite the beauty of their intrinsic Dedekind\u2013Peano axioms<\/a>,<\/em> they are also fully proven by induction.<\/p>\n

\"{\\displaystyle<\/p>\n

Whole numbers are simply expanded naturals<\/em> into the negative direction, a non-orthogonal mirror view on the same axis if you like. Rational numbers are defined as fractions of such integers<\/em> which may be presented using decimal numbers where they may lose precision already, especially when applied in a computer program using float<\/em>.
\nIts hard to cope with the loss of precision using floats for e.g. 1\/3, which error may even explode in non-linear propagation of uncertainty<\/a> when applied to (exponential) computation<\/a>.<\/p>\n

As mentioned, computer floats have their additional lack of accuracy due to their lack of precision to either end. Here a little chart showing the accurate representable floats according to their mantissa size<\/a> which very well visualizes their lack of linear representation or better, the many holes they leave behind. \"Datei:ExaktThese holes are manifested as so called round-off errors<\/a> and potentially sum up and multiplied, distorting the final result.<\/p>\n

I picked up this material issue in our little cs-class<\/a> with my older son while continuously rotating geometric objects, represented by integer numbers. In our first attempt, we just rounded up the rotation-float-expression. The object’s were continuously rotated and visibly distorted their shape more and more in the process. It was quite fun to watch. We created two solutions for this problem, just using floats or storing the angle for an otherwise axis-aligned shape. A third solution would have been to actually use fractions…<\/p>\n

This reminded me of the fixed compile-time rational arithmetic<\/a> in C++, i.e. std::ratio<\/a> but also std::chrono::duration<\/a>. While I embrace the power of C++ application of constexpr<\/em><\/a> compile time functional expression, I also love to use them at runtime with numbers derived in a non literal constant fashion.<\/p>\n

Hence i indulged myself writing jau::fraction<T><\/a> to dive a little bit deeper into this space and also read about Euclid’s algorithm from Euclid’s Elements ~300 BC, book VII<\/a>.<\/p>\n

Adding literals<\/a> to these fractions renders the code frictionless using the greatest common divisor (gcd)<\/a> to calculate the least common multiple (lcm) with overflow checks<\/a> for addition and subtraction:<\/p>\n

1000_ms == 1_s;\r\n60_s == 1_min;\r\nfraction_i64 a = 1000_ms, b = 1_s, c = a + b;\r\nfraction_i64 i = 1_s\/3_s, j = 4_d, k = i + j;<\/pre>\n
The above shows how to compare and compound fractions of a different base w\/o losing precision at runtime, spending two 64-bit integer values for the signed numerator and unsigned denominator.<\/p>\n
Implemented Time in C++<\/h3>\n
I probably won’t live beyond year 2262, which is the limit when using a signed 64-bit nanosecond std::chrono::time_point<\/a>. However, I may reach beyond year 2038, which is the ceiling by using a struct timespec<\/a> on 32-bit platforms having tv_sec<\/em> only last for 68 years since 1970 Unix Epoch. Both limitations are of historical nature and I believe we should do better and foremost more accurate.<\/p>\n
Of course, we already have 64-bit variants of struct timespec<\/em> designed and supported by underlying newer kernels\/OS. We still lack of proper user-land libc support on GNU\/Linux to my knowledge, including pthreads. Therefor it is best advised to utilize a 64-bit system. This is also true for embedded systems, especially since the modern architecture also provides a more efficient cash load and store implementation for atomic operations<\/a>. C++ memory-model slides<\/a> and SC-DRF std::memory_order<\/a> might be of interest.<\/p>\n
To provide at least a timeless notion of a time point storage type today, I introduced jau::fraction_timespec<\/a>. This new type is simply an enforced 64-bit signed struct timespec<\/em> with the capability to convert from and to fractions and supporting all customary time retrieval<\/a>, sleep<\/a> and pthreads-based wait_until()<\/a> and wait_for()<\/a> functions.<\/p>\n
    fraction_timespec<\/a> t0 = getMonotonicTime()<\/a>;\r\n    \/\/ do something\r\n\r\n    \/\/ Exact duration\r\n    fraction_timespec<\/a> td_1 = getMonotonicTime()<\/a> - t0;\r\n\r\n    \/\/ or for durations <= 292 years\r\n    fraction_i64 td_2 = (getMonotonicTime()<\/a> - t0).to_fraction_i64()<\/a>;\r\n    sleep_for( td_2 + 1_ms ); \/\/ sleep for measured period + 1 ms\r\n\r\n    \/\/ same sleep as above, but expressed in absolute time\r\n    fraction_timespec<\/a> absolute_time = getMonotonicTime()<\/a> + td_2;\r\n    sleep_until<\/a>( absolute_time + 1_ms ); \r\n<\/pre>\n
And here the fine details of wait for a condition variable in time limited fashion. When using a condition predicate loop to ensure no spurious wake-up preemptively ends waiting for the condition variable event or timeout, it is always recommended to use wait_until()<\/a> using the absolute timeout time computed once before said loop. Example from latch::wait_for()<\/a>:<\/p>\n
     std::unique_lock<std::mutex> lock(mtx_cd);\r\n     const fraction_timespec<\/a> timeout_time = getMonotonicTime()<\/a> + timeout_duration;\r\n     while( 0 < count ) {\r\n         std::cv_status s = wait_until(cv, lock, timeout_time);\r\n         if( 0 == count ) {\r\n             return true;\r\n         }\r\n         if( std::cv_status::timeout == s ) {\r\n             return false;\r\n         }\r\n     }\r\n<\/pre>\n
Note that the implemented time functions may operate on monotonic or wall-clock time, as supported by the underlying pthread_cond_clockwait()<\/em><\/a> if available and user-library kernel clock_nanosleep()<\/a>, <\/em>both still using the aforementioned struct timeval<\/em> – only timeless on 64-bit platforms.<\/p>\n
All of the above is now used in Direct-BT<\/a>.<\/p>\n
… and this ends my little dive into fraction and times for today \ud83d\ude09<\/p>\n","protected":false},"excerpt":{"rendered":"
Natural numbers are defined as the sequence of numbers fully defined by their initial value, its successor and the successor of its successor and so forth. Despite the beauty of their intrinsic Dedekind\u2013Peano axioms, they are also fully proven by induction.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[59,3,50,58],"tags":[51,52,13,63,33,60,62,61],"class_list":["post-1049","post","type-post","status-publish","format-standard","hentry","category-c-language","category-computer-stuff","category-direct_bt","category-computer-languages","tag-c","tag-direct-bt","tag-embedded-device","tag-fractions","tag-linux","tag-memory-model","tag-precision","tag-time"],"_links":{"self":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts\/1049","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/comments?post=1049"}],"version-history":[{"count":15,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts\/1049\/revisions"}],"predecessor-version":[{"id":1064,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts\/1049\/revisions\/1064"}],"wp:attachment":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/media?parent=1049"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/categories?post=1049"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/tags?post=1049"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}