Skip to content

Instantly share code, notes, and snippets.

View tompng's full-sized avatar

tomoya ishida tompng

148 followers · 30 following
View GitHub Profile
@tompng
tompng / log2_log10_bs.rb
Last active September 24, 2025 15:10
log2 log10 asymptotic binary splitting
# log(10): [[(1/8), 10], [(1/15), 13], [(1/24), 7]]
# log(2): [[(1/8), 3], [(1/15), 4], [(1/24), 2]]
def print_logn_params(base)
value_factors = {}
(8..30).each do |n|
num = (1+1r/n)
(0..30).each do |exp|
v = num ** exp
break if v > 2 * base
@tompng
tompng / faster_exp.rb
Last active September 15, 2025 12:33
def exp_bs(x, prec)
# Taylor series of exp can be converted to continued fraction as:
# exp(x)-1 = x*(1+x/2*(1+x/3*(1+x/4*(1+x/5*(1+...)))))
# Binary splitting can be applied to this continued fraction as:
# (1 + a0/a1 + x/a1 * (1 + b0/b1 + x/b1 * rest))
# (1 + ((a0+x)*b1+x*b0)/(a1*b1) + (x*x)/(a1*b1) * rest)
x = BigDecimal(x)
step = (1..).bsearch { |k| Math.lgamma(k)[0] / Math.log(10) - k * x.exponent > prec }
ms = (1..step).map { [0, BigDecimal(it)] }
while ms.size > 1
@tompng
tompng / rdoc_yard_example1.rb
Created August 30, 2025 05:16
module YARD
class Parser; end
class TagHandler; end
class ParseResult; end
def self.process(comment, code_object)
result = Parser.parse(comment)
tag_handler = TagHandler.new(code_object)
result.tags.each do |name, arg|
tag_handler.handle(name, arg)
@tompng
tompng / sqrt_with_mult.rb
Created August 24, 2025 13:53
def sqrt(x, prec)
y = BigDecimal(Math.sqrt(x.to_f))
yinv = BigDecimal(1 / y.to_f)
(0..prec.bit_length).reverse_each do |i|
p = [[(prec >> i) + 2, BigDecimal.double_fig].max, prec].min
yinv = yinv.mult(BigDecimal(2).sub(y * yinv, p / 2), p / 2)
yinv = yinv.mult(BigDecimal(2).sub(y * yinv, p), p)
y = (y + x * yinv).div(2, p)
end
y
@tompng
tompng / app_example.rb
Last active August 23, 2025 17:53
RackOnRactors::Minitra::Routes.draw do
before do
@foo = rand(1000)
end
get "/longlonglong" do
raise if Ractor.main?
"hello! " * @foo + request_header.inspect
end
end
@tompng
tompng / ntt_mult.rb
Last active August 17, 2025 04:37
NTT(Number Theorem Transform) multiplication
# Reference: https://qiita.com/AngrySadEight/items/0dfde26060daaf6a2fda
BASES = [29, 26, 24]
SHIFT = 27
class NTT
attr_reader :p
def initialize(base, shift)
@base = base
@tompng
tompng / light_2d.html
Created August 5, 2025 08:25
<body>
<script>
const canvas = document.createElement('canvas')
document.body.appendChild(canvas)
const size = canvas.width = canvas.height = 800
const ctx = canvas.getContext('2d')
const circles = [
{ x: 0.2, y: 0.6, r: 0.1 },
{ x: 0.7, y: 0.3, r: 0.07 },
@tompng
tompng / manyzero.rb
Created July 27, 2025 14:16
float num with many zeros: 1.1795176680648731e+39 == 1179517668064873100000000000000008388608.0
def euclidsolve(cx, cy, c, small)
return euclidsolve(cy, cx, c, small).reverse if cx > cy
# cx <= cy
# x * cx + y * cy = c + small
# p [cx.to_f, cy.to_f, c.to_f, small.to_f]
if small >= cy
# cx <= cy, c < cy
# cx*x + cy*y == c + small
# x=0; cy*y == c + small
return [0, 1]
@tompng
tompng / bigdecimal_snippets.rb
Created July 18, 2025 18:20
# size_t 32bit
# docker run -v `pwd`:/bigdecimal --rm -ti arm32v7/ruby bash
# unused defs
code = File.read('ext/bigdecimal/bigdecimal.c')
header = File.read('ext/bigdecimal/bigdecimal.h')
defs = code.scan(/#define ([a-zA-Z_0-9]+)/).uniq
hdefs = header.scan(/#define ([a-zA-Z_0-9]+)/).uniq
defs |= hdefs.select{header.scan(/[a-zA-Z_0-9]+/).count(it[0])==1}
pp defs.map{[it[0], code.scan(/[a-zA-Z_0-9]+/).count(it[0])]}.sort_by(&:last)
@tompng
tompng / divmod_by_mult.rb
Last active July 20, 2025 18:59
# returns (1<<(size + x.bit_length)) / x
def inv(x, size)
x_size = x.bit_length
bl = size.bit_length
n = 2
y = (1 << (n + 2)) / (x >> (x_size - 2))
(0..bl).reverse_each do |i|
n2 = [(size >> i) + 2, size].min
# y = (1<<(x_size + n)) / x